在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 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]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
思路
1. 遍历法（线性查找）
这种方法是通过遍历整个数组来找到 target 的第一个和最后一个位置，时间复杂度为 O(n)，即数组的长度。虽然时间复杂度较高，但对于较小的数组或者不要求最优效率的场景，它是一种简单且直观的解决方案。
实现：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = -1; // 初始化为 -1，表示没有找到
res[1] = -1;
// 查找第一个出现的位置
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
res[0] = i;
break; // 找到第一个出现的位置，退出循环
}
}
// 查找最后一个出现的位置
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] == target) {
res[1] = i;
break; // 找到最后一个出现的位置，退出循环
}
}
return res;
}
}
2. 双指针法
在这个方法中，我们使用两个指针，分别从数组的两端向中间靠近，找出第一个和最后一个目标值。这种方法通常用于数组已经排序或者部分有序的情况。时间复杂度为 O(n)，比遍历法稍微优化，但仍然不如二分查找高效。
实现：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = res[1] = -1; // 默认返回 -1, -1
// 从左边开始找到第一个 target
int left = 0, right = nums.length - 1;
while (left <= right) {
if (nums[left] == target) {
res[0] = left;
break;
}
left++;
}
// 从右边开始找到最后一个 target
left = nums.length - 1; // 重置 left 指针
while (left >= 0) {
if (nums[left] == target) {
res[1] = left;
break;
}
left--;
}
return res;
}
}
3. 哈希表（Hash Map）
这种方法是使用一个哈希表来存储 target 出现的位置。时间复杂度为 O(n)，需要额外的空间来存储位置。如果目标数组中只有一个 target，或者有多个但排序不重要，这种方法可能会有用。然而在这个问题的上下文中，因为数组是排序的，所以哈希表不是最优解。
import java.util.HashMap;
class Solution {
public int[] searchRange(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
int[] res = new int[2];
res[0] = res[1] = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
if (!map.containsKey("first")) {
map.put("first", i); // 第一个出现的位置
}
map.put("last", i); // 最后一个出现的位置
}
}
if (map.containsKey("first") && map.containsKey("last")) {
res[0] = map.get("first");
res[1] = map.get("last");
}
return res;
}
}
4. 利用 Java 内置的 Arrays.binarySearch
我们可以先通过 Arrays.binarySearch 方法找到 target 在数组中的任意位置，然后从该位置向左和向右扩展来寻找第一个和最后一个位置。这种方法实际上与二分查找非常类似，稍微简化了代码，但仍然是 O(log n) 时间复杂度。
import java.util.Arrays;
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = res[1] = -1;
// 使用 binarySearch 找到 target 的任意位置
int index = Arrays.binarySearch(nums, target);
if (index < 0) {
return res; // 如果没找到，直接返回 [-1, -1]
}
// 找第一个出现的位置
int left = index;
while (left > 0 && nums[left - 1] == target) {
left--;
}
// 找最后一个出现的位置
int right = index;
while (right < nums.length - 1 && nums[right + 1] == target) {
right++;
}
res[0] = left;
res[1] = right;
return res;
}
}