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

法一：类似#第一个只出现一次的字符# https://blog.nowcoder.net/n/6aa6f3ed254041a88572510af837616e

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        #统计每个数字出现的次数
        mydict={} 
        for i in data:
            if i not in mydict:
                mydict[i]=1
            else:
                mydict[i]=mydict[i]+1                  
        #找到k出现的次数
        
        if k not in mydict:
            return 0
        return mydict[k]

时间复杂度：O(n)

空间复杂度：O(n)

法二：列表的count方法

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        return data.count(k)

法三: 从头开始找到第一个值为k的元素，再计算连续的k的个数即可。缺点：没有利用好有序数组的特性。

时间复杂度：O(n)。

空间复杂度：O(1)。

法四：二分法.用二分查找找到k+0.5和k−0.5应该出现的位置，二者相减就是k出现的次数。 举例：找k=3出现的次数。

data: 1 2 3 3 3 3 4 5

indx: 0 1 2 3 4 5 6 7

3.5应该在indx=6的位置，2.5应该在indx=2的位置。

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

看到有序数组，就要立马想到用二分查找，一般都能解决问题并且优化时间复杂度。

时间复杂度 O(logn)：二分法通常时间复杂度都是O(logn)

空间复杂度 O(1)：只用到整数型的数据类型，常数项级别