网站的关键词,微网站开发北京,桐乡市住房建设局网站,贸易公司logo设计文章目录1. 题目2. 解题2.1 超时解2.2 优化1. 题目
请你设计一个数据结构#xff0c;它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类#xff1a;
RangeFreqQuery(int[] arr) 用下标从…
文章目录1. 题目2. 解题2.1 超时解2.2 优化1. 题目
请你设计一个数据结构它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 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 次。来源力扣LeetCode 链接https://leetcode-cn.com/problems/range-frequency-queries 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 超时解
存储每个位置的每个数的出现次数的前缀和
class RangeFreqQuery {vectorunordered_mapint,int presum;
public:RangeFreqQuery(vectorint arr) {presum.reserve(arr.size());presum.emplace_back(unordered_mapint,int());presum[0][arr[0]] 1;for(int i 1; i arr.size(); i){presum.emplace_back(presum.back());if(presum[i-1].find(arr[i]) presum[i-1].end())presum[i][arr[i]] 1;elsepresum[i][arr[i]] presum[i-1][arr[i]]1;}}int query(int left, int right, int value) {if(presum[right].find(value) presum[right].end())return 0;if(left 0 || presum[left-1].find(value) presum[left-1].end())return presum[right][value];return presum[right][value] - presum[left-1][value];}
};2.2 优化
记录同一种数字的所有的位置进行二分查找 left 和 right 的 位置
class RangeFreqQuery {unordered_mapint, vectorint pos; // 数字出现的位置
public:RangeFreqQuery(vectorint arr) {for(int i 0; i arr.size(); i){pos[arr[i]].push_back(i);}}int query(int left, int right, int value) {if(pos.find(value) pos.end()) return 0;auto it1 lower_bound(pos[value].begin(), pos[value].end(), left);auto it2 upper_bound(pos[value].begin(), pos[value].end(), right);return it2-it1;}
};524 ms 245.6 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
