【剑指Offer】数字在排序数组中出现的次数 解题报告（Python）

【剑指Offer】数字在排序数组中出现的次数 解题报告（Python）

标签（空格分隔）： 剑指Offer

---

题目地址：https://www.nowcoder.com/ta/coding-interviews

题目描述：

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

解题方法

看到有序，使用二分查找。

使用二分找到这段连续的k的最左边的位置，最右边的位置，两个相减+1就是长度了。

代码：

# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
num = 0
if data:
first = self.getFirstK(data, k , 0, len(data) - 1)
last = self.getLastK(data, k, 0, len(data) - 1)
if first > -1 and last > -1:
num = last - first + 1
return num def getFirstK(self, data, k, start, end):
if start > end:
return -1
mid = (start + end) / 2
midD = data[mid]
if midD > k:
end = mid - 1
elif midD < k:
start = mid + 1
else:
if (mid == 0) or (mid > 0 and data[mid - 1] != k):
return mid
else:
end = mid - 1
return self.getFirstK(data, k, start, end) def getLastK(self, data, k, start, end):
if start > end:
return -1
mid = (start + end) / 2
midD = data[mid]
if midD > k:
end = mid - 1
elif midD < k:
start = mid + 1
else:
if (mid == len(data) - 1) or (mid < len(data) - 1 and data[mid + 1] != k):
return mid
else:
start = mid + 1
return self.getLastK(data, k, start, end)#复制粘贴搞错了。。

Date

2018 年 3 月 24 日 – 周六，校园里很多正在拍毕业照的研三学生～～