LeetCode | 在排序数组中查找元素的第一个和最后一个位置
569 字
3 分钟
LeetCode | 在排序数组中查找元素的第一个和最后一个位置
分类：二分查找 / 数组
题目
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1]讲解
这道题要找的是 target 出现的最左边位置和最右边位置。因为数组已经按照非递减顺序排列，所以相同的数字一定是连续挨在一起的。
这题可以直接复用 搜索插入位置 里的思路：写一个 lower_bound 函数，找第一个大于等于某个值的位置，然后调用两次。
第一次查找：第一个 >= target 的位置。这就是 target 应该出现的最左边位置。
如果这个位置越界，或者这个位置的值不是 target，说明数组里没有 target，直接返回 [-1, -1]。这里要注意：如果 start == len(nums)，那么 nums[start] 会越界。
但是这段代码不会报错，因为 Python 的 or 会短路计算。左边 start == len(nums) 如果已经是 True，右边的 nums[start] != target 就不会再执行。所以这个判断是安全的。
第二次查找：第一个 >= target + 1 的位置。这个位置前面的一个位置，就是 target 出现的最后一个位置。
复杂度
- 暴力做法：
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
- 时间复杂度：
- 二分查找：
- 时间复杂度：
O(log(n)) - 空间复杂度：
O(1)
- 时间复杂度：
代码
源码
from typing import List
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: def lower_bound(target): left = 0 right = len(nums)
while left < right: mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 else: right = mid
return left
start = lower_bound(target) if start == len(nums) or nums[start] != target: return [-1, -1]
end = lower_bound(target + 1) - 1 return [start, end]测试
from src.python._034_Find_First_and_Last_Position_of_Element_in_Sorted_Array import Solution
sol = Solution()
assert sol.searchRange([5, 7, 7, 8, 8, 10], 8) == [3, 4]assert sol.searchRange([5, 7, 7, 8, 8, 10], 6) == [-1, -1]assert sol.searchRange([], 0) == [-1, -1]assert sol.searchRange([1], 1) == [0, 0]
print("PASS")参考资料
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
LeetCode | 在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/相关文章智能推荐
1
LeetCode | 寻找两个正序数组的中位数
LeetCodeLeetCode 寻找两个正序数组的中位数题解：用二分查找切分位置，在 O(log(min(m,n))) 时间内求中位数。
2
LeetCode | 搜索旋转排序数组
LeetCodeLeetCode 搜索旋转排序数组题解：在旋转数组中判断有序半区，再用二分缩小范围。
3
LeetCode | 寻找旋转排序数组中的最小值
LeetCodeLeetCode 寻找旋转排序数组中的最小值题解：比较 nums[mid] 与 nums[right]，定位旋转断点。
4
LeetCode | 搜索插入位置
LeetCodeLeetCode 搜索插入位置题解：用二分查找在升序数组中找到目标位置或插入位置。
5
LeetCode | 搜索二维矩阵
LeetCodeLeetCode 搜索二维矩阵题解：把矩阵看作一维数组做二分，或者先定位行再二分查找。
随机文章随机推荐
评论区
--
总访问量
--
访客数
音乐
暂未播放
0:000:00
文章
66
分类
16
标签
93
总字数
477,284
运行时长
0 天
最后活动
0 天前
