您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)C++中怎么利用LeetCode尋找旋轉(zhuǎn)有序數(shù)組的最小值,文章內(nèi)容質(zhì)量較高,因此小編分享給大家做個(gè)參考,希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
Note:
This is a follow up problem to Find Minimum in Rotated Sorted Array.
Would allow duplicates affect the run-time complexity? How and why?
這道尋找旋轉(zhuǎn)有序重復(fù)數(shù)組的最小值是之前那道 Find Minimum in Rotated Sorted Array 的拓展,當(dāng)數(shù)組中存在大量的重復(fù)數(shù)字時(shí),就會(huì)破壞二分查找法的機(jī)制,將無法取得 O(lgn) 的時(shí)間復(fù)雜度,又將會(huì)回到簡(jiǎn)單粗暴的 O(n),比如這兩種情況:{2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} 和 {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2},可以發(fā)現(xiàn),當(dāng)?shù)谝粋€(gè)數(shù)字和最后一個(gè)數(shù)字,還有中間那個(gè)數(shù)字全部相等的時(shí)候,二分查找法就崩潰了,因?yàn)樗鼰o法判斷到底該去左半邊還是右半邊。這種情況下,將右指針左移一位(或者將左指針右移一位),略過一個(gè)相同數(shù)字,這對(duì)結(jié)果不會(huì)產(chǎn)生影響,因?yàn)橹皇侨サ袅艘粋€(gè)相同的,然后對(duì)剩余的部分繼續(xù)用二分查找法,在最壞的情況下,比如數(shù)組所有元素都相同,時(shí)間復(fù)雜度會(huì)升到 O(n),參見代碼如下:
解法一:
class Solution { public: int findMin(vector<int>& nums) { int left = 0, right = (int)nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else if (nums[mid] < nums[right]) right = mid; else --right; } return nums[right]; } };
跟之前那道 Find Minimum in Rotated Sorted Array 一樣,還是可以用分治法 Divide and Conquer 來解,不過寫法跟之前那道略有不同,只有在 nums[start] < nums[end] 的時(shí)候,才能返回 nums[start],等于的時(shí)候不能返回,比如 [3, 1, 3] 這個(gè)數(shù)組,或者當(dāng) start 等于 end 成立的時(shí)候,也可以直接返回 nums[start],后面的操作跟之前那道題相同,每次將區(qū)間 [start, end] 從中間 mid 位置分為兩段,分別調(diào)用遞歸函數(shù),并比較返回值,每次取返回值較小的那個(gè)即可,參見代碼如下:
解法二:
class Solution { public: int findMin(vector<int>& nums) { return helper(nums, 0, (int)nums.size() - 1); } int helper(vector<int>& nums, int start, int end) { if (start == end) return nums[start]; if (nums[start] < nums[end]) return nums[start]; int mid = (start + end) / 2; return min(helper(nums, start, mid), helper(nums, mid + 1, end)); } };
關(guān)于C++中怎么利用LeetCode尋找旋轉(zhuǎn)有序數(shù)組的最小值就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò),可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。