兰州网站建站,wordpress扁平化中文主题下载,上海网站设计与,网页设计经典范例5186. 区间内查询数字的频率
请你设计一个数据结构#xff0c;它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类#xff1a;
RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 ar…5186. 区间内查询数字的频率
请你设计一个数据结构它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 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 10510^51051 arr[i], value 10410^41040 left right arr.length调用 query 不超过 $10^5 $次。
解题思路
使用map维护某个值在数组中曾经出现的下标key为数组中的元素value为一个数组记录下对于key值在数组中曾经出现的下标在构建map的时候我们按下标从小到大就可以保证value内的下标是有序的。
当我们需要返回子数组 arr[left…right] 中 value 的 频率 的时候我们只需要在map中找到value出现的下标数组通过二分查找找出第一个大于或者等于left的下标l以及找出第一个大于right的下标r而位于这两个下标之间的元素即为子数组 arr[left…right] 中 出现过的value只需要通过r-l求出区间的长度即求出了对应value出现的频率。
代码
class RangeFreqQuery {
private:unordered_mapint, vectorint m;
public:RangeFreqQuery(vectorint arr) {for (int i 0; i arr.size(); i) {m[arr[i]].push_back(i);}}int query(int left, int right, int value) {if (m[value].size() 0) return 0;auto cur m[value];auto l lower_bound(cur.begin(), cur.end(), left), r upper_bound(cur.begin(), cur.end(), right);return r - l;}
};/*** Your RangeFreqQuery object will be instantiated and called as such:* RangeFreqQuery* obj new RangeFreqQuery(arr);* int param_1 obj-query(left,right,value);*/
