给定一个按照升序排列的整数数组 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]
这题是让在升序数组中找到目标值,所以最容易想到的就是二分法查找,但这里数组中是有重复的元素,如果找到的是重复的就要返回重复元素的第一个和最后一个的位置,那么找到后分别往前和往后继续查找然后再比较key值。
class Solution {
public int[] searchRange(int[] nums, int target) {
int find = searchRangeHelper(nums, target);
//如果没找到,返回{-1, -1}
if (find == -1)
return new int[]{-1, -1};
int left = find - 1;
int right = find + 1;
//查看前面是否还有target
while (left >= 0 && nums[left] == target)
left--;
//查看后面是否还有target
while (right < nums.length && nums[right] == target)
right++;
return new int[]{left + 1, right - 1};
}
//二分法查找
private int searchRangeHelper(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int midVal = nums[mid];
if (midVal < target) {
low = mid + 1;
} else if (midVal > target) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
}
复杂度分析:
时间复杂度:O(logN),这里 N 是数组的长度 空间复杂度:O(1),只使用了常数个数的辅助变量
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array