37 数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。例如：输入排序数组[1,2,3,3,3,3,4,5]和数字3，输出4。

解题思路

核心思想：使用二分查找找到数字的第一次出现和最后一次出现的位置。

关键步骤：

1. 二分查找第一个等于target的位置
2. 二分查找最后一个等于target的位置
3. 出现次数 = 最后位置 - 首位置 + 1

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

Python 实现

def get_number_of_k(nums, k):
    """
    统计数字k在排序数组中出现的次数

    Args:
        nums: 排序数组
        k: 目标数字

    Returns:
        int: 出现的次数
    """
    if not nums:
        return 0

    # 找第一个等于k的位置
    def get_first_k(left, right):
        if left > right:
            return -1

        mid = (left + right) // 2
        if nums[mid] < k:
            return get_first_k(mid + 1, right)
        elif nums[mid] > k:
            return get_first_k(left, mid - 1)
        elif mid == 0 or nums[mid - 1] < k:
            return mid
        else:
            return get_first_k(left, mid - 1)

    # 找最后一个等于k的位置
    def get_last_k(left, right):
        if left > right:
            return -1

        mid = (left + right) // 2
        if nums[mid] < k:
            return get_last_k(mid + 1, right)
        elif nums[mid] > k:
            return get_last_k(left, mid - 1)
        elif mid == len(nums) - 1 or nums[mid + 1] > k:
            return mid
        else:
            return get_last_k(mid + 1, right)

    first = get_first_k(0, len(nums) - 1)
    last = get_last_k(0, len(nums) - 1)

    if first == -1 or last == -1:
        return 0

    return last - first + 1


# 测试代码
if __name__ == "__main__":
    test_cases = [
        ([1, 2, 3, 3, 3, 3, 4, 5], 3),
        ([1, 2, 3, 4, 5], 3),
        ([1, 1, 1, 1], 1),
        ([1, 2, 3], 4),
    ]

    for nums, k in test_cases:
        print(f"{nums}中{k}出现的次数: {get_number_of_k(nums, k)}")

# 输出:
# [1, 2, 3, 3, 3, 3, 4, 5]中3出现的次数: 4
# [1, 2, 3, 4, 5]中3出现的次数: 1
# [1, 1, 1, 1]中1出现的次数: 4
# [1, 2, 3]中4出现的次数: 0

图解

示例: [1,2,3,3,3,3,4,5], k=3

找第一个3:
left=0, right=7, mid=3, nums[3]=3
检查nums[2]=2<3，找到第一个3 → 位置3

找最后一个3:
left=0, right=7, mid=3, nums[3]=3
检查nums[4]=3不>3，继续找
left=4, right=7, mid=5, nums[5]=3
检查nums[6]=4>3，找到最后一个3 → 位置6

次数: 6 - 3 + 1 = 4