Leetcode 2080

题目要求

给定数组，多次查询给定范围内的子数组中某元素的出现频率

核心算法和原理

• 建立每个元素的「下标列表」，即将每个元素的下标放到一个数组里。由于可以线性访问数组所以一定单调递增

• 问题转换为：对于元素value的下标列表，求位于[left, right]内的元素个数

• 直接二分每个元素的下标列表，找到第一个≥left和>right的位置相减即可

代码

class RangeFreqQuery {
public:
    unordered_map<int, vector<int>> indexes;
    RangeFreqQuery(vector<int>& arr) {
        for (int i = 0; i < arr.size(); i++) {
            indexes[arr[i]].emplace_back(i);
        }
    }

    int query(int left, int right, int value) {
        if (!indexes.count(value)) {
            return 0;
        }
        vector<int>& index = indexes[value];
        int l = -1, r = index.size();
        int midl, midr;
        // cout << 1 << endl;
        while (l + 1 < r) {
            // cout << l << " " << r << endl;
            midl = (l + r) / 2;
            (index[midl] >= left ? r : l) = midl;
        }
        midl = r;


        // cout << 2 << endl;
        l = -1, r = index.size();
        while (l + 1 < r) {
            // cout << l << " " << r << endl;

            midr = (l + r) / 2;
            (index[midr] > right ? r : l) = midr;
        }

        midr = r;

        return midr - midl;
    }
};

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