JZX轻语：简
LeetCode 2080 - 区间内查询数字的频率
发表于2025年02月18日
一开始想到的是前缀和的思路，但由于题目并非是针对某种小数据集的查询（比如小写字母），而是任意数字，因此前缀和会占用大量的空间。因此，我们可以使用哈希表来记录每个数字所出现的位置，然后对于每次查询，使用二分查找来计算区间内的频率：对于查询区间[left, right]，我们先找到第一个大于等于left的位置l，然后找到第一个大于right的位置r，则出现的频率为r - l。
手动实现二分查找的做法：
class RangeFreqQuery {
public:
RangeFreqQuery(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) occ_map[arr[i]].push_back(i);
}
int query(int left, int right, int value) {
if (occ_map.find(value) == occ_map.end()) return 0;
const auto& occ = occ_map[value];
int lo = 0, hi = occ.size() - 1;
while (lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
if (occ[mid] >= left) hi = mid - 1;
else lo = mid + 1;
}
if (lo >= occ.size()) return 0;
int l = lo;
lo = l, hi = occ.size() - 1;
while(lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
if (occ[mid] > right) hi = mid - 1;
else lo = mid + 1;
}
int r = lo;
return r - l;
}
private:
unordered_map<int, vector<int>> occ_map;
};使用STL算法库的做法：
class RangeFreqQuery {
public:
RangeFreqQuery(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) occ_map[arr[i]].push_back(i);
}
int query(int left, int right, int value) {
if (occ_map.find(value) == occ_map.end()) return 0;
const auto& occ = occ_map[value];
return std::distance(
std::lower_bound(occ.begin(), occ.end(), left),
std::upper_bound(occ.begin(), occ.end(), right)
);
}
private:
unordered_map<int, vector<int>> occ_map;
};