文章目录
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 次。
2. 解题
2.1 超时解
- 存储每个位置的每个数的出现次数的前缀和
class RangeFreqQuery { vector<unordered_map<int,int>> presum; public: RangeFreqQuery(vector<int>& arr) { presum.reserve(arr.size()); presum.emplace_back(unordered_map<int,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; else presum[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_map<int, vector<int>> pos; // 数字出现的位置 public: RangeFreqQuery(vector<int>& 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++
