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

╰+哭是因爲堅強的太久メ 2022-05-04 14:56 177阅读 0赞

## 题目描述 ##

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

时间限制：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