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

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

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

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 (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) - 1for l < r {mid := (l + r) / 2if 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) - 1for l < r {mid := (l + r) / 2if 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)-1for l <= r {mid := l + (r - l) / 2if pos[mid] <= target {l = mid + 1} else {r = mid - 1}}return l
}func lowerBound(pos []int, target int) int {l, r := 0, len(pos) - 1for l <= r {mid := l + (r - l) / 2if 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);*/