区间内查询数字的频率

难度: Medium

请你设计一个数据结构，它能求出给定子数组内一个给定值的频率。

子数组中一个值的频率指的是这个子数组中这个值的出现次数。

请你实现 RangeFreqQuery 类：

RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的频率。

一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内的中间一段连续元素。

示例 1：

输入：
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
[null, 1, 2]

解释：
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。

提示：

1 <= arr.length <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
调用 query 不超过 10⁵ 次。

Submission

运行时间: 498 ms

内存: 53.7 MB

class RangeFreqQuery:
 
    def __init__(self, arr: List[int]):
        self.occurs = defaultdict(list)
        for i, v in enumerate(arr):
            self.occurs[v].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        inds = self.occurs[value]
        ind1 = bisect_left(inds, left)
        ind2 = bisect_right(inds, right)
        return ind2 - ind1



# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)

Explain

这个题解采用哈希表来存储每个元素在数组中出现的所有下标位置。这样，对于任何查询，我们可以迅速定位到特定元素在数组中的位置，并利用二分搜索来快速找到子数组范围内该元素的出现频率。初始化时，遍历数组，将每个元素的索引存储到哈希表中。查询时，首先检查给定值的所有索引列表，然后使用二分查找找到子数组范围内的第一个和最后一个位置，最后通过这两个位置的索引差来计算频率。

时间复杂度: O(n) for construction, O(log k) per query

空间复杂度: O(n)

# Class definition for the RangeFreqQuery
class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        # Dictionary to store occurrences of each value along with their indices
        self.occurs = defaultdict(list)
        for i, v in enumerate(arr):
            self.occurs[v].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        # Get the list of indices for the given value
        inds = self.occurs[value]
        # Find the left boundary of indices within the range
        ind1 = bisect_left(inds, left)
        # Find the right boundary of indices within the range
        ind2 = bisect_right(inds, right)
        # The frequency is the difference between the right and left boundaries
        return ind2 - ind1

# Usage example:
# obj = RangeFreqQuery(arr)
# result = obj.query(left, right, value)

Explore

哈希表被选用是因为它提供了非常快的平均时间复杂度为O(1)的查找、插入和删除操作，适合频繁查找某个元素的索引。使用哈希表，我们可以快速定位到任何元素的所有出现位置。相比之下，如果使用平衡树（如AVL树或红黑树），虽然可以保持元素的有序性，但在频繁的插入和查找操作中，时间复杂度为O(log n)，效率低于哈希表。而直接使用数组存储索引会造成空间浪费，且查找特定元素的所有索引不如哈希表高效。

题解的代码中确实没有显式处理`value`不在`occurs`字典中的情况。通常，这种情况应当返回频率为0，因为字典中没有该元素的记录即表示该元素在数组中没有出现。在实际应用中，应在查询前检查`value`是否存在于`occurs`中，如果不存在应直接返回0。这是防止在调用`bisect_left`和`bisect_right`时因列表为空而引发错误。

`bisect_left`和`bisect_right`都是二分查找的变种，用于在有序列表中查找元素的插入位置。`bisect_left`返回的是插入位置，保证插入后列表中该位置左侧的所有元素都小于或等于要插入的元素，因此它找到的是在指定范围内的左边界（即从`left`开始的第一个位置）。`bisect_right`返回的是元素应该插入的最右侧位置，即使插入后该位置右侧的所有元素都大于要插入的元素，因此它找到的是在指定范围内的右边界。使用这两个方法可以精确地确定子数组范围内元素的首次和最后一次出现位置，从而计算出频率。

如果`left`和`right`的范围超出了实际数组的边界，`bisect_left`和`bisect_right`仍然可以正确处理这种情况。`bisect_left`将返回一个不小于`left`的最小索引，即使`left`小于数组的最小索引。同样，`bisect_right`将返回一个不大于`right`的最大索引，即使`right`大于数组的最大索引。这意味着，即使范围超出了数组边界，这两个函数仍然会返回有效的索引值，从而正确地计算出范围内元素的频率。