37.数字在排序数组中出现的次数(python)

题目描述

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

1 # -*- coding:utf-8 -*-
2 class Solution:
3     def GetNumberOfK(self, data, k):
4         # write code here
5         count = 0
6         for i in range(len(data)):
7             if data[i]==k:
8                 count+=1
9         return count

二分法：

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def GetNumberOfK(self, data, k):
 4         # write code here
 5         def getLeftPos(data,left,right):
 6             while left <= right:
 7                 mid = (left +right)//2
 8                 if data[mid]<k:
 9                     left=mid+1
10                 else:
11                     right = mid-1
12             return left
13         def getRightPos(data,left,right):
14             while left <=right:
15                 mid = (left+right)//2
16                 if data[mid]<=k:
17                     left = mid+1
18                 else:
19                     right = mid-1
20             return right
21         left = 0
22         right = len(data)-1
23         leftPos = getLeftPos(data,left,right)
24         rightPos = getRightPos(data,left,right)
25         return rightPos-leftPos+1
26