題目：
給定一個按照升序排列的整數陣列 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]
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一個非遞減陣列
- -109 <= target <= 109
首先分析一下題目：
陣列是一個升序的陣列，沒有說陣列中的元素是單一的，那么他的回傳值的情況有：
1、當 target 在陣列中找到了，如果 target 在陣列中不止 1 個，那么回傳的是 【i,j】;
2、當 target 在陣列中只有一個，回傳的是 【i,i】;
3、沒有找到回傳 【-1，-1】.
常規想法：
直接遍歷陣列找到 target 出現的第一個位置，記為 i, 繼續遍歷陣列，找下一個出現的位置，記為 j ,
當然 j 可能會變化，因為可能下一個位置還是 target，當遍歷到不是 target 結束回圈，i j 的位置就是我們的結果，
之后就是分情況討論了，【如下面代碼的第一種解法】
從運行情況看，這顯然不是最好的做法，那么該怎么做呢？二分法
利用二分思想先找其左邊界，再找其右邊界即可，注意找左邊界的時候，由右側逼近；
找右邊界的時候，由左側逼近，即可，【如下面代碼的第二種解法】
- 第一種解法：
class Solution {
public static int[] searchRange(int[] nums, int target) {
int start = -1, end = -1;
boolean first = false; // 記錄是否是第一次定位到 target
int len = nums.length;
for(int i=0;i<len;i++){
if(!first){
if(target == nums[i]){
start = i;
first = true;
}
} else {
if(target == nums[i]){
end = i;
}
}
}
int[] res = new int[] {-1, -1};
if(first){ // 找到了 target
res[0] = start;
if(end == -1){ // target 出現的次數不止一次
res[1] = start;
} else {
res[1] = end;
}
return res;
}
// 沒有找到 target
return res;
}
}
- 第二種解法：
class Solution {
public static int[] searchRange(int[] nums, int target) {
int[] res = new int[] {-1, -1};
res[0] = findRange(nums, target, true); //找左邊界
res[1] = findRange(nums, target, false); //找右邊界
return res;
}
public static int findRange(int[] nums,int target,boolean left_right){
int res = -1;
int left = 0, right = nums.length - 1, mid;
while(left <= right) { //二分查找
mid = (left + right)>>1;
if(target < nums[mid]) {
right = mid - 1;
} else if(target > nums[mid]) {
left = mid + 1;
} else {
res = mid;
if(left_right) { //往左邊找
right = mid - 1;
} else { //往右邊找
left = mid + 1;
}
}
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/374618.html
標籤：其他