统计一个数字在排序数组中出现的次数。
解题思路:
遍历查找不是本题的最优解,既然给出的是有序数组,所以我们只需要找到目标的左侧和右侧的索引即可。所以我们可以找到本数组当中key+0.5和key-0.5的位置即可得到次数,二分查找将减少时间复杂度。
代码
# -*- coding:utf-8 -*-
class Solution:
def GetIdx(self, data, k):
s = 0
e = len(data) - 1
while (s <= e):
mid = int((e - s) / 2) + s
print(mid)
if data[mid] < k:
s = mid + 1
elif data[mid] > k:
e = mid - 1
return s
def GetNumberOfK(self, data, k):
# write code here
return self.GetIdx(data, k + 0.5) - self.GetIdx(data, k - 0.5)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)