题解 | #数字在升序数组中出现的次数#

数字在升序数组中出现的次数

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100 要求：空间复杂度 O(1)，时间复杂度 O(logn)

题目非常简单，用二分先找到k出现的位置middle，然后从middle的左边右边遍历，复杂度为logn+k出现的次数，空间复杂度1

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # write code here
        if len(data) == 0:
            return 0
        left = 0
        right = len(data) - 1
        middle = (int)((left + right)/2)
        n = 0
        while left <= right:
            if data[middle] == k:
                n += 1
                break;
            elif data[middle] > k:
                right = middle -1
            else :
                left = middle + 1
            middle = (int)((left + right)/2)
        if left >= right:
            return n
        else :
            index = middle + 1
            i = 1
            while (index + i < len(data)) | (index - i >= 0):
                if  index + i < len(data):
                    if data[index + i] == k:
                        n += 1
                if (index - i) >= 0:
                    if data[index - i] == k:
                        n += 1
                i += 1
        return n

解法二：在解法一的基础上优化，先找到k出现的位置middle，然后用二分查找k在start到middle之间第一次出现的位置index_s和middle+1到end之间k最后一次出现的位置index_e，出现的次数n = index_e - index_s + 1

```#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # write code here
        if len(data) == 0:
            return 0
        if (len(data) == 1) & (data[0] == k):
            return 1
        left = 0
        right = len(data) - 1
        middle = (int)((left + right)/2)
        n = 0
        while left < right:
            if data[middle] == k:
                n += 1
                break;
            elif data[middle] > k:
                right = middle -1
            else :
                left = middle + 1
            middle = (int)((left + right)/2)
        if left >= right:
            return n
        else :
            rightl = middle
            index_s = (int)((left + rightl)/2)
            while left < rightl:
                if data[index_s] == k:
                    rightl = index_s - 1;
                    if data[rightl] < k:
                        break
                elif data[index_s] < k:
                    left = index_s + 1
                    if data[left] == k:
                        index_s = left
                        break
                index_s = (int)((left + rightl)/2)
            leftr = middle + 1
            index_e = (int)((leftr + right)/2)
            while leftr < right:
                if data[index_e] == k:
                    leftr = index_e + 1
                    if data[leftr] > k:
                        break
                elif data[index_e] > k:
                    right = index_e - 1
                    if data[right] == k:
                        index_e = right
                        break
                index_e = (int)((leftr + right)/2)
            n = index_e - index_s + 1
        return n