Title Description
Statistics the number of digits in a sorted array.
thinking
The lowest method is still the count count.
Of course, when you look at an ordered array, you should think of the dichotomy, find the duplicate numbers on the left and right, and then subtract the two.
Answer
Method 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)
Method 2, do not use count counting method.
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
Method 3, dichotomy
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):###Find the leftmost digit position in the duplicate number.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):###Find the digit position on the far right of the duplicate number.while left<=right: middle=(left+right)//2 if data[middle]<=k: left=middle+1 else: right=middle-1 return right