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

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(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);
 */