[M二分]lc2080.区间内查询数字的频率(模拟+二分+数据结构+Go二分库函数+知识总结)

文章目录 1. 题目来源2. 题目解析

1. 题目来源

链接：2080. 区间内查询数字的频率

相关：

[M二分] lc34. 在排序数组中查找元素的第一个和最后一个位置(二分+经典)

题单：

待补充 2. 题目解析

本题其实思路很简单的，但是在代码实现上、二分理解上出现了问题，还有一些小坑点啥的…特此记录。

思路：

题目要求 [l, r] 区间中的 value 数量。实际上可以统计每一个 value 所在的下标位置，拿切片进行存储即可。此时构成了一个有序序列，里面存储的都是下标。显然，可以二分求解。只需要找到第一个 大于等于 l 的位置 L，和第一个 大于 r 的位置 R 即可求得 value 的个数即为 R - L。 熟悉 lower_bound、upper_bound 操作的话，就可以直接拿库函数求解 L、R 的位置了。

坑点：

复盘：2025年02月18日19:01:13

我所习惯使用的整数二分模板，在最近 LeetCode 题中使用的都没啥问题，主要还是因为 LeetCode 一般都能保证存在答案，即：二分后的结果一定正确。

当我再使用这个模板处理当前问题的时候，或者说我希望自己去实现 lower_bound、upper_bound 操作的时候，发现板子是用不了的。

具体的，如下：

反例1： 下标列表：【2】 求解区间：【1,2】 显然，lower_bound 求解应该是 0，upper_bound 求解应该是 1 但是，由于我使用的二分模板，l=0, r=len([2])-1=0，连 for 循环都进不去…那么就会直接让 L=R=0… 因为没加结果的判断，导致二分模板求解出来的值和实际上 lower_bound、upper_bound 是不符的。

---

反例2： 下标列表: 【1,2】 求解区间：【5,6】 显然，lower_bound 求解是无解状态，那么会返回下标 2，upper_bound 求解也是无解状态返回 2。那么他们的相减就是正确的。 但是，我的二分模板还是返回了 L=0，R=1 这种结果。因为我的 l,r := 0, n-1 这样的设定下，注定他们和 lower_bound 的返回效果不可通用。

---

思考3：针对左边界、右边界没找到的时候，无效值应该赋哪个？

左右都赋 0 肯定不合适，因为右边界没找到，说明所求的数字远大于当前区间，右边界此时 upper_bound 应该是 n 才对。 左边界赋 0、右边界赋 n 肯定也不合适，左边界这个较小值都没找到，右边界肯定也是没有的，但此时结果相减却是 n。 左右都赋 n 合适，满足 lower_bound、upper_bound 的非法情况的赋值操作。因为都没找到的情况下，都赋值为 n，那么相减后，结果依然是 0。右边界在没找到的情况喜爱，赋值为 n，也是合理的。相当于给数组中添加一个很大的数作为右侧哨兵。 此时左边界没找到，则右边界一定没找到，则结果为 0。此时左边界找到为 L，则结果为 R-L 也是满足答案的。

因为靠打印，知道了二分模板实现的有问题，但又在非法情况判断这块的赋值上又出了问题。

还是这些基础知识掌握的不牢固啊。

---

总的来说，本篇文章需要解决两个问题：

自身使用的二分模板有缺陷，二分求解完成后，根据需要需要验证答案正确性。需要搞一个 GoLang 版本的 lower_bound、upper_bound 操作的函数使用。

---

时间复杂度： O ( n ) O(n) O(n)空间复杂度： O ( 1 ) O(1) O(1)

---

type RangeFreqQuery struct { arr map[int][]int } func Constructor(arr []int) RangeFreqQuery { list := map[int][]int{} for i, v := range arr { list[v] = append(list[v], i) } return RangeFreqQuery{arr: list} } func (this *RangeFreqQuery) Query(left int, right int, value int) int { list := this.arr[value] if len(list) == 0 { return 0 } L, R := 0, 0 // 寻找第一个 大于等于 left 的元素位置 l, r := 0, len(list) - 1 for l < r { mid := (l + r) / 2 if list[mid] < left { l = mid + 1 } else { r = mid } } // 如果不存在，则等于其长度。因为 R 也会这样处理，如果不存在等于其长度。 // 但 R 的处理是合理的，当 R 不存在的时候 L 可能会存在，那么此时相减就是合理的。 // 如果 R 不存在，这里的 L 不存在却赋成 0 / -1 这类非法值，反而相减就不合理了。 if list[l] < left { L = len(list) } else { L = l } // 寻找第一个 大于 right 的元素位置 l, r = 0, len(list) - 1 for l < r { mid := (l + r) / 2 if list[mid] > right { r = mid } else { l = mid + 1 } } if list[l] <= right { R = len(list) } else { R = l } return R - L } /** * Your RangeFreqQuery object will be instantiated and called as such: * obj := Constructor(arr); * param_1 := obj.Query(left,right,value); */

---

自实现 lower_bound、upper_bound 写法： 作为算法模板：

type RangeFreqQuery struct { arr map[int][]int } func Constructor(arr []int) RangeFreqQuery { list := map[int][]int{} for i, v := range arr { list[v] = append(list[v], i) } return RangeFreqQuery{arr: list} } func (this *RangeFreqQuery) Query(left int, right int, value int) int { list := this.arr[value] L := lowerBound(list, left) R := upperBound(list, right) return R - L } func upperBound(pos []int, target int) int { l, r := 0, len(pos)-1 for l <= r { mid := l + (r - l) / 2 if pos[mid] <= target { l = mid + 1 } else { r = mid - 1 } } return l } func lowerBound(pos []int, target int) int { l, r := 0, len(pos) - 1 for l <= r { mid := l + (r - l) / 2 if pos[mid] < target { l = mid + 1 } else { r = mid - 1 } } return l } /** * Your RangeFreqQuery object will be instantiated and called as such: * obj := Constructor(arr); * param_1 := obj.Query(left,right,value); */

---

使用 golang 库函数 SearchInts 来处理。

sort 包的函数，可参考这个博主的博文：

[Go语言tips01]浅谈sort包

简单来说 func SearchInts(a []int, x int) int 就是相当于 lower_bound 操作。至于 upper_bound 一般都可以用 right+1 配合 lower_bound 进行实现。

type RangeFreqQuery struct { arr map[int][]int } func Constructor(arr []int) RangeFreqQuery { list := map[int][]int{} for i, v := range arr { list[v] = append(list[v], i) } return RangeFreqQuery{arr: list} } func (this *RangeFreqQuery) Query(left int, right int, value int) int { list := this.arr[value] L := sort.SearchInts(list, left) R := sort.SearchInts(list, right + 1) return R - L } /** * Your RangeFreqQuery object will be instantiated and called as such: * obj := Constructor(arr); * param_1 := obj.Query(left,right,value); */