34.在排序數(shù)組中尋找元素的第一個和最后一個位置
給你一個按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target钦铺。請你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置诫尽。
如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]臀防。
你必須設(shè)計并實現(xiàn)時間復(fù)雜度為 O(log n) 的算法解決此問題。
鏈接：https://leetcode.cn/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ù)組
- nums 是一個非遞減數(shù)組
思路分析：
這也是一道典型的二分查找的問題边败，與之前不同的是袱衷，需要找出元素第一次出現(xiàn)的位置和最后一次出現(xiàn)的位置，而若是元素沒有出現(xiàn)過的話笑窜，需要返回數(shù)組[-1,-1]致燥，這里可以在最后利用一個判斷語句進(jìn)行判斷，如下：
if (a <= b && b < (int)nums.size() && nums[a] == target && nums[b] == target)
{
return vector<int>{a, b};
}
return {-1,-1};
那么總的套路還是一樣的排截，仍然可以參考我之前總結(jié)的二分查找的多個不同模板進(jìn)行求解嫌蚤。
(3條消息) 【LeetCode704.二分查找】——二分查找方法匯總_一粒蛋TT的博客-CSDN博客
左分右邊法：
class Solution {
public:
//求出第一次出現(xiàn)位置
int target(vector<int>& nums, int target) {
int l = -1;
int r = (int)nums.size();
while ((l + 1) != r)
{
int m = (l + r) / 2;
//cout << "m=" << m<<endl;
if (nums[m] < target)
{
l = m;
}
else
{
r = m;
}
}
cout << "target1=" << r << endl;
return r;
}
//求出最后一次出現(xiàn)的位置
int targettwo(vector<int>& nums, int target)
{
int l = -1;
int r = (int)nums.size();
while ((l + 1) != r)
{
int m = (l + r) / 2;
//cout << "m=" << m<<endl;
if (nums[m] <= target)
{
l = m;
}
else
{
r = m;
}
}
cout << "target2=" << l << endl;
return l;
}
vector<int> searchRange(vector<int>& nums, int target )
{
int a = this->target(nums, target );
int b = this->targettwo(nums, target );
if (a <= b && b < (int)nums.size() && nums[a] == target && nums[b] == target)
{
return vector<int>{a, b};
}
return {-1,-1};
}
};
左閉右閉法：
class Solution {
public:
int binarySearch(vector<int>& nums, int target, bool lower) {
int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
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;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
return vector<int>{leftIdx, rightIdx};
}
return vector<int>{-1, -1};
}
};
利用STL庫：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) {
return {-1, -1};
}
int leftIdx = lower_bound(nums.begin(), nums.end(), target)-nums.begin();
int rightIdx = upper_bound(nums.begin(), nums.end(), target)-1-nums.begin();
if(leftIdx<=rightIdx && rightIdx<nums.size() && nums[leftIdx]==target && nums[rightIdx]==target) {
return {leftIdx, rightIdx};
}
return {-1, -1};
}
};
利用CPP中的STL庫函數(shù)，我們可以更快的直接求出元素的第一次出現(xiàn)位置以及最后一次出現(xiàn)的位置断傲。這部分代碼參考了leetcode隨心源的題解脱吱。
總的來說，該題是對之前簡單二分查找的一個延伸拓展认罩。
后續(xù)也會堅持更新我的LeetCode刷題筆記箱蝠，歡迎大家關(guān)注我，一起學(xué)習(xí)。
如果這篇文章對你有幫助宦搬，或者你喜歡這篇題解牙瓢，可以給我點個贊哦。
CSDN同步更新床三，歡迎關(guān)注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode學(xué)習(xí)筆記,HTML+CSS+JS,數(shù)據(jù)結(jié)構(gòu)領(lǐng)域博主
往期回顧：
LeetCode367.有效的完全平方數(shù)
LeetCode69.x的平方根
LeetCode35.搜索插入位置
LeetCode704.二分查找
