给定一个长度为 n的非降序数组和一个非负数整数k,要求统计 k 在数组中出现的次数 数据范围:0≤几≤1000,0≤k≤100,数组中每个元表的值满足0≤ val ≤ 100 要求:空间复杂度 0(1),时间复杂度 O(logn)

可以考虑使用二分查找来实现时间复杂度为 O(logn) 的算法。

首先，我们可以通过二分查找找到 k 第一次出现的位置和最后一次出现的位置，然后将它们的下标相减即可得到 k 在数组中出现的次数。

具体实现如下：

def count_k(nums, k):
    # 二分查找 k 第一次出现的位置
    left, right = 0, len(nums) - 1
    first = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= k:
            right = mid - 1
        else:
            left = mid + 1
        if nums[mid] == k:
            first = mid

    # 如果 k 不在数组中，直接返回 0
    if first == -1:
        return 0

    # 二分查找 k 最后一次出现的位置
    left, right = 0, len(nums) - 1
    last = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] > k:
            right = mid - 1
        else:
            left = mid + 1
        if nums[mid] == k:
            last = mid

    # 返回 k 在数组中出现的次数
    return last - first + 1

该算法的空间复杂度为 O(1)，时间复杂度为 O(logn)。