給定一個按照升序排列的整數(shù)數(shù)組 nums妖啥，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置
如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。
進(jìn)階：
你可以設(shè)計并實(shí)現(xiàn)時間復(fù)雜度為 O(log n) 的算法解決此問題嗎俱笛？
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
示例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]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一個非遞減數(shù)組
-109 <= target <= 109
Java解法
思路：
- 跟昨天的類型很相似，就數(shù)組結(jié)構(gòu)有變化传趾，采用相同的二分查找來進(jìn)行操作
- 這里要注意命中時前后的延伸問題迎膜，OK~
package sj.shimmer.algorithm.ten_3;
/**
* Created by SJ on 2021/2/15.
*/
class D22 {
public static void main(String[] args) {
int[] result1 = searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8);
int[] result2 = searchRange(new int[]{5,7,7,8,8,10},6);
int[] result3 = searchRange(new int[]{},0);
int[] result4 = searchRange(new int[]{2,2},2);
System.out.println(result1[0]+","+result1[1]);
System.out.println(result2[0]+","+result2[1]);
System.out.println(result3[0]+","+result3[1]);
System.out.println(result4[0]+","+result4[1]);
}
public static int[] searchRange(int[] nums, int target) {
int[] result = new int[]{-1,-1};
if (nums != null&&nums.length!=0) {
int length = nums.length;
int start = 0;
int end = length-1;
while (start<=end) {
int mid = (start+end)/2;
if (nums[mid]==target) {
//求左邊界
result[0] = mid;
result[1] = mid;
for (int i = mid-1; i >= 0; i--) {
if (nums[i] ==target) {
result[0] = i;
}else {
break;
}
}
//求右邊界
for (int i = mid+1; i < length; i++) {
if (nums[i] ==target) {
result[1] = i;
}else {
break;
}
}
return result;
} else if (nums[mid] < target) {
start = mid+1;
}else {
end = mid-1;
}
}
}
return result;
}
}
image
官方解
-
二分查找
主要思想一致，但查找目標(biāo)有較小的差異浆兰，相比較而言磕仅，時間效率差不多珊豹，空間上稍微好一點(diǎn)
核心思路：
- 要找的就是數(shù)組中「第一個等于target 的位置」（記為 leftIdx）和「第一個大于 target 的位置減一」（記為 rightIdx）
- 復(fù)用方法導(dǎo)致了這里有些理解麻煩，但核心都是查找某個具體有限定的位置，相比較我的先命中再查邊界在重復(fù)數(shù)據(jù)較多時更有優(yōu)勢
public int[] searchRange(int[] nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) { return new int[]{leftIdx, rightIdx}; } return new int[]{-1, -1}; } public int binarySearch(int[] nums, int target, boolean lower) { int left = 0, right = nums.length - 1, ans = nums.length; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; }image時間復(fù)雜度： O(log n)
空間復(fù)雜度：O(1)
