leetcode5186.区间内查询数字的频率（周赛，中等）

看到调用query不超过10^5次，则query()必须控制在O(logn)以内

自己的思路： 定义一个unordered_map<int, set> hash; //值->set的下标映射

	auto le = hash[value].lower_bound(left);
	for (; *le <= right && le != hash[value].end(); le++) {
	   cnt++;
	}
	return cnt;
1
2
3
4
5

用的set计算两个迭代器之间的距离，复杂度达到O(n)，部分样例超时！！！
优化思路：想让迭代器之间距离的计算缩减到O(logn)以内的话，必须使用顺序存储的容器
正解：
定义一个unordered_map<int, vector> hash; //值->vector下标映射

class RangeFreqQuery {
public:
    unordered_map<int, vector<int>> hash;  
    RangeFreqQuery(vector<int>& arr) {
        
        int n = arr.size();
        for (int i = 0; i < n; ++i) {
            hash[arr[i]].push_back(i);
        }
    }
    int query(int left, int right, int value) {
        
        if (!hash.count(value)) return 0;
        auto le = lower_bound(hash[value].begin(), hash[value].end(), left);
        //下面这段代码没有也可以，因为函数的目的是是计算两个迭代器之间的距离
        //if (le != hash[value].end() && *le > right) return 0; //有这段代码的话，加上le != hash[value].end() ！！！
        auto b = upper_bound(hash[value].begin(), hash[value].end(), right);
        return b - le;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

易错点：
在lower_bound()后使用 *le的时候必须先判断(le != hash[value].end()！！！