5186. 區間內查詢數字的頻率

請你設計一個數據結構，它能求出給定子數組內一個給定值的 頻率 。

子數組中一個值的 頻率 指的是這個子數組中這個值的出現次數。

請你實現 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 $次。

解題思路

使用map維護某個值在數組中曾經出現的下標，key為數組中的元素，value為一個數組，記錄下對于key值在數組中曾經出現的下標，在構建map的時候，我們按下標從小到大，就可以保證value內的下標是有序的。

當我們需要返回子數組 arr[left…right] 中 value 的 頻率 的時候，我們只需要在map中找到value出現的下標數組，通過二分查找，找出第一個大于或者等于left的下標l，以及找出第一個大于right的下標r，而位于這兩個下標之間的元素即為子數組 arr[left…right] 中 出現過的value，只需要通過r-l求出區間的長度，即求出了對應value出現的頻率。

代碼

class RangeFreqQuery {
private:unordered_map<int, vector<int>> m;
public:RangeFreqQuery(vector<int> &arr) {for (int i = 0; i < arr.size(); ++i) {m[arr[i]].push_back(i);}}int query(int left, int right, int value) {if (m[value].size() == 0) return 0;auto &cur = m[value];auto l = lower_bound(cur.begin(), cur.end(), left), r = upper_bound(cur.begin(), cur.end(), right);return r - l;}
};/*** Your RangeFreqQuery object will be instantiated and called as such:* RangeFreqQuery* obj = new RangeFreqQuery(arr);* int param_1 = obj->query(left,right,value);*/