题目描述
统计一个数字在排序数组中出现的次数
思路
最贱的方法依旧是count计数。。
当然，，看到有序数组就应该想到二分法，找到重复数字左边和右边的数字，然后两个相减就可以了
解答
方法1 count
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if not data or len(data) ==0:
return 0
return data.count(k)
方法2，不用count的计数方法
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if not data or len(data) ==0:
return 0
num = 0
for i in data:
if i == k:
num += 1
return num
方法3，二分法
class Solution:
def GetNumberOfK(self, data, k):
left=0
right=len(data)-1
leftk=self.getleftK(data,k,left,right)
rightk=self.getrightK(data,k,left,right)
return rightk-leftk+1
def getleftK(self,data,k,left,right):###查找重复数字中最左边的那个数字位置
while left<=right:
middle=(left+right)//2
if data[middle]<k:
left=middle+1
else:
right=middle-1
return left
def getrightK(self,data,k,left,right):###查找重复数字最右边的那个数字位置
while left<=right:
middle=(left+right)//2
if data[middle]<=k:
left=middle+1
else:
right=middle-1
return right