题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，要求建立一个数据结构，使得输入一个区间和一个目标值，可以返回目标值在区间内的出现频率。

思路分享

  • 用二分可以加速有序数组的查找效率，所以陆爻齐开始的思路是，截取区间数组，排序，然后二分查找上界与下界之差。然后在最后的几个样例超时了。

  • 这时就显现灵神题解的强大了，如何快速查找一个区间内有几个这个数字呢？只要先把各个数字的下标用 map 记录即可，每个数字对应一串下标，由于初始化时就是从前往后，所以不用排序。

  • 记录下标后，不是查询时会给区间嘛，用区间的上下界，在对应目标值的下标数组中，二分查找自己的位置，然后做差就可以得到这个区间内数字的频率了，毕竟此时这两位置之间就是之前数字的下标。

    https://leetcode.cn/problems/range-frequency-queries/solutions/1113439/tong-ji-wei-zhi-er-fen-wei-zhi-by-endles-8l9u/

  • 这里补充一下，ranges 库的 upper 和 lower_bound 分别可以看作，找第一个大于 val 的下标和找第一个大于等于 val 的下标。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class RangeFreqQuery {
public:
    RangeFreqQuery(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            rec[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int value) {
        auto it = rec.find(value);
        if (it == rec.end()) return 0;
        vector<int> &arr = it->second;
        return ranges::upper_bound(arr, right)-ranges::lower_bound(arr, left);
    }
private:
    unordered_map<int, vector<int>> rec;
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);
 */