小编给大家分享一下LeetCode中如何在排序数组中查找数字,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!
统计一个数字在排序数组中出现的次数。
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
右边界-左边界+1
(数组存在该数字的情况下)class Solution:
def search(self, nums: List[int], target: int) -> int:
def binarySearch(isleft):
# 传入flag isleft, 标记当前是查找左边界还是右边界
s, e = 0, len(nums) - 1
# 初始化结果为None
res = None
while s <= e:
m = (s + e) >> 1
if nums[m] == target:
if isleft:
# 当前查找的是左边界, 更新结果为等于target的更小的下标, 同时向左继续查找
res = m if res is None else min(res, m)
e = m - 1
else:
# 当前查找的是右边界, 更新结果为等于target的更大的下标, 同时向右继续查找
res = m if res is None else max(res, m)
s = m + 1
elif nums[m] < target:
s = m + 1
else:
e = m - 1
return res
left = binarySearch(True)
if left is None:
# 如果左边界不存在, 则说明整个数组没有target, 直接返回0
return 0
right = binarySearch(False)
# 最终结果就是右边界-左边界+1
return right - left + 1
看完了这篇文章,相信你对“LeetCode中如何在排序数组中查找数字”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。