数字在升序数组中出现的次数

数字在升序数组中出现的次数_牛客题霸_牛客网

问题简述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

思路

• 两次二分查找，分别得到左右两个端点，相减即为出现次数；

  二分查找的是 x 的插入位置，不一定要在 arr 中出现；

Python

class Solution:
    def GetNumberOfK(self , arr: List[int], x: int) -> int:
        
        def bisect(arr, x, fn):
            l, r = 0, len(arr)
            while l < r:
                m = (l + r) // 2
                if fn(arr[m], x):
                    l = m + 1
                else:
                    r = m
            return l
        
        l = bisect(arr, x, lambda x1, x2: x1 < x2)
        r = bisect(arr, x, lambda x1, x2: x1 <= x2)
        return r - l