Design a data structure to find the frequency of a given value in a given subarray.
The frequency of a value in a subarray is the number of occurrences of that value in the subarray.
Implement the RangeFreqQuery
class:
RangeFreqQuery(int[] arr)
Constructs an instance of the class with the given 0-indexed integer arrayarr
.int query(int left, int right, int value)
Returns the frequency ofvalue
in the subarrayarr[left...right]
.
A subarray is a contiguous sequence of elements within an array. arr[left...right]
denotes the subarray that contains the elements of nums
between indices left
and right
(inclusive).
Example 1:
Input ["RangeFreqQuery", "query", "query"] [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]] Output
[null, 1, 2]
Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.
Constraints:
1 <= arr.length <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
- At most
105
calls will be made toquery
Solution: Hashtable + Binary Search
Time complexity: Init: O(max(arr) + n), query: O(logn)
Space complexity: O(max(arr) + n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class RangeFreqQuery { public: RangeFreqQuery(vector<int>& arr) : s_(10001) { for (int i = 0; i < arr.size(); ++i) s_[arr[i]].push_back(i); } int query(int left, int right, int value) { const auto& m = s_[value]; if (m.empty()) return 0; auto r = prev(upper_bound(begin(m), end(m), right)); auto l = lower_bound(begin(m), end(m), left); return r - l + 1; } private: vector<vector<int>> s_; }; /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery* obj = new RangeFreqQuery(arr); * int param_1 = obj->query(left,right,value); */ |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment