您好,登錄后才能下訂單哦!
這篇文章主要講解了“C++如何實現(xiàn)在有序數(shù)組中查找元素的第一個和最后一個位置”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“C++如何實現(xiàn)在有序數(shù)組中查找元素的第一個和最后一個位置”吧!
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]
這道題讓我們在一個有序整數(shù)數(shù)組中尋找相同目標(biāo)值的起始和結(jié)束位置,而且限定了時間復(fù)雜度為 O(logn),這是典型的二分查找法的時間復(fù)雜度,所以這里也需要用此方法,思路是首先對原數(shù)組使用二分查找法,找出其中一個目標(biāo)值的位置,然后向兩邊搜索找出起始和結(jié)束的位置,代碼如下:
解法一:
class Solution { public: vector<int> searchRange(vector<int>& 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<int>& 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); } };
可能有些人會覺得上面的算法不是嚴(yán)格意義上的 O(logn) 的算法,因為在最壞的情況下會變成 O(n),比如當(dāng)數(shù)組里的數(shù)全是目標(biāo)值的話,從中間向兩邊找邊界就會一直遍歷完整個數(shù)組,那么下面來看一種真正意義上的 O(logn) 的算法,使用兩次二分查找法,第一次找到左邊界,第二次調(diào)用找到右邊界即可,具體代碼如下:
解法二:
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> 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ù),來同時查找出第一個和最后一個位置。如何只用查找第一個大于等于目標(biāo)值的二分函數(shù)來查找整個范圍呢,這里用到了一個小 trick,首先來查找起始位置的 target,就是在數(shù)組中查找第一個大于等于 target 的位置,當(dāng)返回的位置越界,或者該位置上的值不等于 target 時,表示數(shù)組中沒有 target,直接返回 {-1, -1} 即可。若查找到了 target 值,則再查找第一個大于等于 target+1 的位置,然后把返回的位置減1,就是 target 的最后一個位置,即便是返回的值越界了,減1后也不會越界,這樣就實現(xiàn)了使用一個二分查找函數(shù)來解題啦,參見代碼如下:
解法三:
class Solution { public: vector<int> searchRange(vector<int>& 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<int>& 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++如何實現(xiàn)在有序數(shù)組中查找元素的第一個和最后一個位置”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對C++如何實現(xiàn)在有序數(shù)組中查找元素的第一個和最后一個位置這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。