本文小編為大家詳細(xì)介紹“怎么用C++在有序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“怎么用C++在有序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識(shí)吧。
成都創(chuàng)新互聯(lián)公司成立與2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目做網(wǎng)站、網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元巴林左旗做網(wǎng)站,已為上家服務(wù),為巴林左旗各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm"s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
這道題讓我們?cè)谝粋€(gè)有序整數(shù)數(shù)組中尋找相同目標(biāo)值的起始和結(jié)束位置，而且限定了時(shí)間復(fù)雜度為 O(logn)，這是典型的二分查找法的時(shí)間復(fù)雜度，所以這里也需要用此方法，思路是首先對(duì)原數(shù)組使用二分查找法，找出其中一個(gè)目標(biāo)值的位置，然后向兩邊搜索找出起始和結(jié)束的位置，代碼如下：
解法一:
重慶分公司
重慶分公司
class Solution {
public:
vector searchRange(vector& nums, int target) {
int idx = search(nums, 0, nums.size() - 1, target);
if (idx == -1) return {-1, -1};
int left = idx, right = idx;
while (left > 0 && nums[left - 1] == nums[idx]) --left;
while (right < nums.size() - 1 && nums[right + 1] == nums[idx]) ++right;
return {left, right};
}
int search(vector& nums, int left, int right, int target) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) return search(nums, mid + 1, right, target);
else return search(nums, left, mid - 1, target);
}
}; 可能有些人會(huì)覺得上面的算法不是嚴(yán)格意義上的 O(logn) 的算法，因?yàn)樵谧顗牡那闆r下會(huì)變成 O(n)，比如當(dāng)數(shù)組里的數(shù)全是目標(biāo)值的話，從中間向兩邊找邊界就會(huì)一直遍歷完整個(gè)數(shù)組，那么下面來看一種真正意義上的 O(logn) 的算法，使用兩次二分查找法，第一次找到左邊界，第二次調(diào)用找到右邊界即可，具體代碼如下：
解法二：
class Solution {
public:
vector searchRange(vector& nums, int target) {
vector res(2, -1);
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (right == nums.size() || nums[right] != target) return res;
res[0] = right;
right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) left = mid + 1;
else right = mid;
}
res[1] = right - 1;
return res;
}
}; 其實(shí)我們也可以只使用一個(gè)二分查找的子函數(shù)，來同時(shí)查找出第一個(gè)和最后一個(gè)位置。如何只用查找第一個(gè)大于等于目標(biāo)值的二分函數(shù)來查找整個(gè)范圍呢，這里用到了一個(gè)小 trick，首先來查找起始位置的 target，就是在數(shù)組中查找第一個(gè)大于等于 target 的位置，當(dāng)返回的位置越界，或者該位置上的值不等于 target 時(shí)，表示數(shù)組中沒有 target，直接返回 {-1, -1} 即可。若查找到了 target 值，則再查找第一個(gè)大于等于 target+1 的位置，然后把返回的位置減1，就是 target 的最后一個(gè)位置，即便是返回的值越界了，減1后也不會(huì)越界，這樣就實(shí)現(xiàn)了使用一個(gè)二分查找函數(shù)來解題啦，參見代碼如下：
解法三：
class Solution {
public:
vector searchRange(vector& nums, int target) {
int start = firstGreaterEqual(nums, target);
if (start == nums.size() || nums[start] != target) return {-1, -1};
return {start, firstGreaterEqual(nums, target + 1) - 1};
}
int firstGreaterEqual(vector& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return right;
}
}; 讀到這里，這篇“怎么用C++在有序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
