目标
请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 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^5
- 1 <= arr[i], value <= 10^4
- 0 <= left <= right < arr.length
- 调用 query 不超过 10^5 次。
思路
设计一个数据结构，能够求出给定元素在子数组中的出现次数。
可以使用哈希表保存每个元素的下标列表（从小到大），查询时根据 value 获取下标列表，二分查找左边界的下界（第一个大于等于左边界的下标）和右边界的上界（最后一个小于等于右边界的下标）。注意二分查找的范围是 0 ~ list.size()，但是比较的则是原数组中的下标。构建时间复杂度为 O(n)，查询时间复杂度为 O(logn)。
代码
/**
* @date 2025-02-18 15:57
*/
public class RangeFreqQuery {
public Map<Integer, List<Integer>> valueIndexMap = new HashMap<>();
public RangeFreqQuery(int[] arr) {
for (int i = 0; i < arr.length; i++) {
valueIndexMap.putIfAbsent(arr[i], new ArrayList<>());
valueIndexMap.get(arr[i]).add(i);
}
}
public int query(int left, int right, int value) {
List<Integer> list = valueIndexMap.get(value);
if (list == null) {
return 0;
}
return getUpperBound(right, list) - getLowerBound(left, list) + 1;
}
public int getUpperBound(int target, List<Integer> list) {
int l = 0, r = list.size() - 1;
int m = l + (r - l) / 2;
while (l <= r) {
if (list.get(m) > target) {
r = m - 1;
} else {
l = m + 1;
}
m = l + (r - l) / 2;
}
return r;
}
public int getLowerBound(int target, List<Integer> list) {
int l = 0, r = list.size() - 1;
int m = l + (r - l) / 2;
while (l <= r) {
if (list.get(m) < target) {
l = m + 1;
} else {
r = m - 1;
}
m = l + (r - l) / 2;
}
return l;
}
}
性能
