剑指offer之037-数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。

思路

整体用二分法,找到头和尾。

因为data中都是整数,所以可以稍微变一下,不是搜索k的两个位置,而是搜索k-0.5和k+0.5

这两个数应该插入的位置,然后相减即可。

def biSearch(data, k):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] > k:
            high = mid - 1
        elif data[mid] < k:
            low = mid + 1
    return high

def GetNumberOfK(data, k):
    # write code here
    if not data: return 0
    return biSearch(data, k+0.5) - biSearch(data, k-0.5)

print(GetNumberOfK([3,3,3, 4],3))

关于明柳梦少

坚守自己的原则,不随波逐流。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注