算法设计

剑指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))
隐藏作者信息

关于明柳梦少

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