在排序数组中查找元素的第一个和最后一个位置(二分、lower_bound、upper_bound)
程序员文章站
2022-06-22 16:35:57
Leetcode 每日一题题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置难度: 中等解题思路: 这道题题意很明显,就是二分查找。即为C++中的 lower_bound 和 upper_bound 函数。这里给出python3的版本。题解:class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: if len(nums) == 0:...
Leetcode 每日一题
题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置
难度: 中等
解题思路: 这道题题意很明显,就是二分查找。即为C++中的 lower_bound 和 upper_bound 函数。这里给出python3的版本。
题解:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) == 0:
return (-1, -1)
# 向左二分
def lower_bound(nums, target):
l, r = 0, len(nums) - 1
res = -1
if l == r and target == nums[l]:
return 0
while l < r:
mid = (l + r) // 2 # 向下取整
if target <= nums[mid]:
r = mid
res = mid
else:
l = mid + 1
if res == -1 and target == nums[r]: # 右边界
res = r
if res != -1 and target != nums[res]: # 未找到
res = -1
return res
# 向右二分
def upper_bound(nums, target):
l, r = 0, len(nums) - 1
res = -1
if l == r and target == nums[l]:
return 0
while l < r:
mid = (l + r) // 2 + 1 # 向上取整
if target < nums[mid]:
r = mid - 1
else:
l = mid
res = mid
if res == -1 and target == nums[r]: # 左边界
res = r
if res != -1 and target != nums[res]: # 未找到
res = -1
return res
return (lower_bound(nums, target),upper_bound(nums, target))
本文地址:https://blog.csdn.net/qq_37753409/article/details/110422750
上一篇: 移掉K位数字(单调栈)
下一篇: js中的数组对象排序分析
推荐阅读
-
C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)
-
在排序数组中查找元素的第一个和最后一个位置、变形二分法
-
#leetcode刷题之路34-在排序数组中查找元素的第一个和最后一个位置
-
34. 在排序数组中查找元素的第一个和最后一个位置
-
Leetcode No.34 在排序数组中查找元素的第一个和最后一个位置
-
在排序数组中查找元素的第一个和最后一个位置(二分、lower_bound、upper_bound)
-
在排序数组中查找元素的第一个和最后一个位置
-
34. 在排序数组中查找元素的第一个和最后一个位置【二分待完成】
-
leetcode34---在排序数组中查找元素的第一个和最后一个位置
-
34. 在排序数组中查找元素的第一个和最后一个位置