【剑指Offer】37数字在排序数组中出现的次数

题目描述

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

时间限制：1秒；空间限制：32768K；本题知识点：数组

解题思路

思路一

先找循环到第一个相同数的位置索引，然后从中这个位置看判断后面连续的数是否相同，直到出现不相同的数，输出计数结果。

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if data==[]: #考虑所有可能的情况
            return 0
        count = 0
        # 如果有，找到第一个相同数的索引
        for i in range(len(data)):
            if data[i]==k:
                break
        # 循环直到下一个数不相同
        while data[i]==k:
            count += 1
            i += 1
            # 如果是最后一个了则跳出循环
            if i == len(data):
                break
        return count

思路二

用二分查找k第一次出现的位置和最后一次出现的位置。

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        # 二分查找定位k的第一次出现位置和最后一次出现位置
        lower = self.getLower(data,k)
        upper = self.getUpper(data,k)
        return upper-lower+1
    # 获取k第一次出现的下标
    def getLower(self, data, k):
        start = 0
        end = len(data)-1
        mid = (start + end) // 2
        while start <= end:
            if data[mid] < k: #注意区别
                start = mid + 1
            else:
                end = mid - 1
            mid = (start + end) // 2
        return start
    # 获取k最后一次出现的下标
    def getUpper(self, data, k):
        start = 0
        end = len(data)-1
        mid = (start + end) // 2
        while start <= end:
            if data[mid] <= k: #注意区别
                start = mid + 1
            else:
                end = mid - 1
            mid = (start + end) // 2
        return end