夯实算法-在排序数组中查找元素的第一个和最后一个位置
2022-12-14 本文已影响0人
在中国喝Java
题目：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]
复制代码
示例 3：
输入： nums = [], target = 0
输出： [-1,-1]
复制代码
提示：
- <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo><</mo><mo>=</mo><mi>n</mi><mi>u</mi><mi>m</mi><mi>s</mi><mi mathvariant="normal">.</mi><mi>l</mi><mi>e</mi><mi>n</mi><mi>g</mi><mi>t</mi><mi>h</mi><mo><</mo><mo>=</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">0 <= nums.length <= 10^5</annotation></semantics></math>0<=nums.length<=105
- <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>−</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo><</mo><mo>=</mo><mi>n</mi><mi>u</mi><mi>m</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo><</mo><mo>=</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup></mrow><annotation encoding="application/x-tex">-10^9 <= nums[i] <= 10^9</annotation></semantics></math>−109 <=nums[i] <=109
-
nums是一个非递减数组 - <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>−</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo><</mo><mo>=</mo><mi>t</mi><mi>a</mi><mi>r</mi><mi>g</mi><mi>e</mi><mi>t</mi><mo><</mo><mo>=</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup></mrow><annotation encoding="application/x-tex">-10^9 <= target <= 10^9</annotation></semantics></math>−109 <=target <=109
解题思路
首先需要理解题意，题目有一定的迷惑性，非递减，也就是升序，但可能会有相等的元素，起始位置，其实就是找target的起始下标：
- 如果target不存在，那就是[-1, -1]
- 如果target只有一个，那么就是[index, index]
- 如果target有重复的，那么就需要返回[lower, upper]，其中i=[lower, upper]，[i]都是等于target的，并且[lower-1] != target，[upper+1] ！= target
先用二分查找到target的index，然后在[0, index-1]，范围内再用二分查找找lower，lower的条件就是[lower] == target并且[lower-1] != target，需要注意的是，查找lower过程中所有元素都是小于等于target的；同理，可以在[index+1，n-1]范围内找upper，upper的条件是[upper+1] != target并且[upper] == target，需要注意的是查找 upper过程中所有元素都是大于等于target的。
查找 lower时，如果某个mid是0，就说明到了最左边了，查找右边时，如果到了n-1，那就到了最右边了。
循环的条件要是left <= right，这是因为传入的范围都是具体的下标，也就是闭区间，所以mid需要走到左右边界。
代码实现
public int[] searchRange(int[] nums, int target) {
int[] result = {
-1, -1
};
int index = Arrays.binarySearch(nums, target);
if (index < 0) {
return result;
}
if (index == 0 || nums[index - 1] != target) {
result[0] = index;
} else {
result[0] = findLower(nums, index - 1, target);
}
if (index == nums.length - 1 || nums[index + 1] != target) {
result[1] = index;
} else {
result[1] = findUpper(nums, index + 1, target);
}
return result;
}
private int findLower(int[] nums, int index, int target) {
int left = 0;
int right = index;
while (left <= right) {
int mid = (left + right) >> 1;
if (nums[mid] == target) {
if (mid == 0 || nums[mid - 1] != target) {
return mid;
}
right = mid - 1;
} else {
if (mid == index - 1 || nums[mid + 1] == target) {
return mid + 1;
}
left = mid + 1;
}
}
return index;
}
private int findUpper(int[] nums, int index, int target) {
int left = index;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (nums[mid] == target) {
if (mid == nums.length - 1 || nums[mid + 1] != target) {
return mid;
}
left = mid + 1;
} else {
if (mid == index + 1 || nums[mid - 1] == target) {
return mid - 1;
}
right = mid - 1;
}
}
return index;
}
复制代码
复杂度分析
- 空间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1)
- 时间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(logn)</annotation></semantics></math>O(logn)
