当前位置：首页 > news >正文

LeetCode 热题 100 34. 在排序数组中查找元素的第一个和最后一个位置

news 2025/6/7 5:55:11

LeetCode 热题 100 | 34. 在排序数组中查找元素的第一个和最后一个位置

大家好，今天我们来解决一道经典的算法题——在排序数组中查找元素的第一个和最后一个位置。这道题在 LeetCode 上被标记为中等难度，要求我们在一个按照非递减顺序排列的整数数组中找到目标值的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。题目要求使用时间复杂度为 O(log n) 的算法。下面我将详细讲解解题思路，并附上 Python 代码实现。

问题描述

给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target，找出目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3, 4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1, -1]

示例 3：

输入：nums = [], target = 0
输出：[-1, -1]

解题思路

二分查找：
- 使用二分查找找到目标值的一个位置。
- 从找到的位置开始，向左和向右扩展，找到目标值的起始位置和结束位置。

Python 代码实现

class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""if not nums:return [-1, -1]left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] < target:left = mid + 1elif nums[mid] > target:right = mid - 1else:left = midbreakpos = leftif pos >= len(nums) or nums[pos] != target:return [-1, -1]left, right = 0, 0while (pos + right) < len(nums) and nums[pos + right] == target:right += 1while (pos - left) >= 0 and nums[pos - left] == target:left += 1return [pos - left + 1, pos + right - 1]# 测试示例
print(Solution().searchRange([5,7,7,8,8,10], 8))  # 输出: [3, 4]
print(Solution().searchRange([5,7,7,8,8,10], 6))  # 输出: [-1, -1]
print(Solution().searchRange([], 0))  # 输出: [-1, -1]

代码解析

检查空数组：
- 如果 nums 是空数组，直接返回 [-1, -1]。
二分查找目标值：
- 使用二分查找找到目标值 target 的一个位置。
- 如果 nums[mid] < target，说明目标值在右侧，移动左边界。
- 如果 nums[mid] > target，说明目标值在左侧，移动右边界。
- 如果找到目标值，将 left 设置为当前的 mid，并跳出循环。
验证目标值是否存在：
- 如果 pos 超出数组范围或 nums[pos] 不等于目标值，说明目标值不存在，返回 [-1, -1]。
扩展目标值范围：
- 初始化两个变量 left 和 right，分别用于向左和向右扩展。
- 向右扩展：从 pos 开始，逐步向右检查，直到找到不等于目标值的元素。
- 向左扩展：从 pos 开始，逐步向左检查，直到找到不等于目标值的元素。
计算范围：
- 返回目标值的范围 [pos - left + 1, pos + right - 1]。