[LeetCode] 每日一题 2080. 区间内查询数字的频率
题目链接
题目描述
请你设计一个数据结构,它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery
类:
RangeFreqQuery(int[] arr)
用下标从 0 开始的整数数组arr
构造一个类的实例。int query(int left, int right, int value)
返回子数组arr[left...right]
中value
的 频率 。
一个 子数组 指的是数组中一段连续的元素。arr[left...right]
指的是 nums
中包含下标 left
和 right
在内 的中间一段连续元素。
示例输入
示例
输入:
["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
次。
解题思路
今天的题目要求我们设计一个数据结构,用于查询给定子数组内某个值的频率。为了高效地解决这个问题,我的思路是使用一个 Map
来存储数组中每个值的所有出现位置。具体来说,Map
的键是数组中的值,值是该值在数组中所有出现位置的索引列表
在查询时,我们通过对该列表进行二分查找来找到指定区间内该值的出现次数。具体而言,我们需要使用二分查找找到该值在给定区间 left
和 right
内的上下界,从而快速计算该值在这个区间内出现的次数。通过这种方式,我们能够大大提高查询效率
代码实现
class RangeFreqQuery {
Map<Integer, List<Integer>> existMap = new HashMap<>();
public RangeFreqQuery(int[] arr) {
for (int i = 0; i < arr.length; i++) {
existMap.putIfAbsent(arr[i], new ArrayList<>());
existMap.get(arr[i]).add(i);
}
}
public int query(int left, int right, int value) {
List<Integer> exist = existMap.getOrDefault(value, null);
if (exist == null) {
return 0;
}
// left <= l <= r <= right
int l = findBigger(exist, left);
int r = findSmaller(exist, right);
return r - l + 1;
}
private int findBigger(List<Integer> exist, int target) {
int low = 0, high = exist.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (exist.get(mid) < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
private int findSmaller(List<Integer> exist, int target) {
int low = 0, high = exist.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (exist.get(mid) <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
}
复杂度分析
时间复杂度:
RangeFreqQuery
的构造函数会遍历数组一次,因此时间复杂度为 O(n),其中 n 是数组的长度query
函数每次查询时,我们需要在existMap
中查找值对应的索引列表,并对该列表执行两次二分查找。每次二分查找的时间复杂度是 O(log n),因此查询操作的时间复杂度是 O(log n),其中 n 是该值在数组中的出现次数
空间复杂度:O(n),因为我们需要存储数组中每个值的索引列表,最坏情况下,所有的值都是相同的,因此存储空间为 O(n)
总结
这道题目通过引入 Map
和二分查找,使得频率查询的操作变得高效。通过将数组中每个值的出现位置存储起来,我们能够在查询时迅速找到符合条件的区间,并计算频率。与暴力遍历相比,这种方法能大幅减少查询时间,提高了查询效率。在解决此类区间查询问题时,利用预处理和二分查找是一个非常有效的策略。
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。