子数组中一个值的 频率 指的是这个子数组中这个值的涌现次数。
请你实现 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 <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
调用 query 不超过 105 次。
解题思路剖析1、哈希+二分查找；韶光繁芜度O(nlog(n)),空间繁芜度O(n)
type RangeFreqQuery struct { m map[int][]int}func Constructor(arr []int) RangeFreqQuery { m := make(map[int][]int) for i := 0; i < len(arr); i++ { m[arr[i]] = append(m[arr[i]], i) } return RangeFreqQuery{m: m}}func (this RangeFreqQuery) Query(left int, right int, value int) int { arr := this.m[value] l := lowerBound(arr, left) r := upperBound(arr, right) return r - l}// 返回第一个大于即是target的位置func lowerBound(arr []int, target int) int { left, right := 0, len(arr) for left < right { mid := left + (right-left)/2 if arr[mid] == target { right = mid // 紧缩左边界 } else if arr[mid] < target { left = mid + 1 } else { right = mid } } return left}// 返回第一个大于target的位置func upperBound(arr []int, target int) int { left, right := 0, len(arr) for left < right { mid := left + (right-left)/2 if arr[mid] == target { left = mid + 1 // 紧缩左边界 } else if arr[mid] < target { left = mid + 1 } else { right = mid } } return left}
2、内置函数；韶光繁芜度O(nlog(n)),空间繁芜度O(n)
type RangeFreqQuery struct { m map[int]sort.IntSlice}func Constructor(arr []int) RangeFreqQuery { m := make(map[int]sort.IntSlice) for i := 0; i < len(arr); i++ { m[arr[i]] = append(m[arr[i]], i) } return RangeFreqQuery{m: m}}func (this RangeFreqQuery) Query(left int, right int, value int) int { arr := this.m[value] arr = arr[arr.Search(left):] return arr.Search(right + 1)}
3、内置函数；韶光繁芜度O(nlog(n)),空间繁芜度O(n)
type RangeFreqQuery struct { m map[int][]int}func Constructor(arr []int) RangeFreqQuery { m := make(map[int][]int) for i := 0; i < len(arr); i++ { m[arr[i]] = append(m[arr[i]], i) } return RangeFreqQuery{m: m}}func (this RangeFreqQuery) Query(left int, right int, value int) int { arr := this.m[value] l := sort.SearchInts(arr, left) r := sort.SearchInts(arr, right+1) return r - l}总结
Medium题目，稽核二分查找
