题目描述
统计一个数字在排序数组中出现的次数。
python实现：
# -*- coding:utf-8 -*-
class Solution:
#有序，使用二分查找
def GetNumberOfK(self, data, k):
# write code here
n = len(data)
if n==0:
return 0
start = self.getFisrtPosOfK(data, k)
if start==-1:
return 0
end = self.getLastPosOfK(data, k)
return end-start+1
def getFisrtPosOfK(self, data, k):
n = len(data)
low, high = 0, n-1
while low<=high:
mid = (low+high)/2
if data[mid] == k:
if mid==0 or data[mid]!=data[mid-1]:
return mid
else:
high = mid-1
elif data[mid]>k:
high = mid-1
else:
low = mid+1
return -1#没找到
def getLastPosOfK(self, data, k):
n = len(data)
low, high = 0, n-1
while low<=high:
mid = (low+high)/2
if data[mid] == k:
if mid==n-1 or data[mid]!=data[mid+1]:
return mid
else:
low = mid+1
elif data[mid]>k:
high = mid-1
else:
low = mid+1
return -1#没找到
