目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給定一個按照升序排列的整數陣列 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] <= 109num是一個非遞減陣列-109 <= target <= 109
2、思路
(二分) O ( l o g n ) O(logn) O(logn)
在一個范圍內，查找一個數字，要求找到這個元素的開始位置和結束位置，這個范圍內的數字都是單調遞增的，即具有單調性質，因此可以使用二分來做，
兩次二分，第一次二分查找第一個>=target的位置，第二次二分查找最后一個<=target的位置，查找成功則回傳兩個位置下標，否則回傳[-1,-1]，
實作細節：
- 二分查找時，首先要確定我們要查找的邊界值，保證每次二分縮小區間時，邊界值始終包含在內，
第一次查找起始位置:
-
1、二分的范圍，
l = 0，r = nums.size() - 1，我們去二分查找>=target的最左邊界， -
2、當
nums[mid] >= target時，往左半區域找，r = mid，
-
3、當
nums[mid] < target時， 往右半區域找，l = mid + 1，
- 4、如果
nums[r] != target，說明陣列中不存在目標值target，回傳[-1, -1]，否則我們就找到了第一個>=target的位置L，
第二次查找結束位置：
-
1、二分的范圍，
l = 0，r = nums.size() - 1，我們去二分查找<=target的最右邊界， -
2、當
nums[mid] <= target時，往右半區域找，l = mid，
-
3、當
nums[mid] > target時， 往左半區域找，r = mid - 1，
-
4、找到了最后一個
<=target的位置R，回傳區間[L,R]即可，
時間復雜度分析： 兩次二分查找的時間復雜度為 O ( l o g n ) O(logn) O(logn)，
3、c++代碼
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty()) return {-1,-1};
int l = 0, r = nums.size() - 1; //二分范圍
while( l < r) //查找元素的開始位置
{
int mid = (l + r )/2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if( nums[r] != target) return {-1,-1};
int L = r;
l = 0, r = nums.size() - 1;
while( l < r) //查找元素的結束位置
{
int mid = (l + r + 1)/2;
if(nums[mid] <= target ) l = mid;
else r = mid - 1;
}
return {L,r};
}
};
4、java代碼
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) return new int[]{-1,-1};
int l = 0, r = nums.length - 1; //二分范圍
while( l < r) //查找元素的開始位置
{
int mid = (l + r )/2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if( nums[r] != target) return new int[]{-1,-1};
int L = r;
l = 0; r = nums.length - 1;
while( l < r) //查找元素的結束位置
{
int mid = (l + r + 1)/2;
if(nums[mid] <= target ) l = mid;
else r = mid - 1;
}
return new int[]{L,r};
}
}
原題鏈接： 34. 在排序陣列中查找元素的第一個和最后一個位置
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/294932.html
標籤：java
上一篇：專欄訂閱須知《必讀》