154.?Find Minimum in Rotated Sorted Array II
hard題。
Suppose an array of length?n?sorted in ascending order is?rotated?between?1?and?n?times. For example, the array?nums = [0,1,4,4,5,6,7]?might become:[4,5,6,7,0,1,4]?if it was rotated?4?times.[0,1,4,4,5,6,7]?if it was rotated?7?times.Notice that?rotating?an array?[a[0], a[1], a[2], ..., a[n-1]]?1 time results in the array?[a[n-1], a[0], a[1], a[2], ..., a[n-2]].Given the sorted rotated array?nums?that may contain?duplicates, return?the minimum element of this array.You must decrease the overall operation steps as much as possible.
做這道題之前可以先做153.?Find Minimum in Rotated Sorted Array(medium).?
Suppose an array of length?n?sorted in ascending order is?rotated?between?1?and?n?times. For example, the array?nums = [0,1,2,4,5,6,7]?might become:[4,5,6,7,0,1,2]?if it was rotated?4?times.[0,1,2,4,5,6,7]?if it was rotated?7?times.Notice that?rotating?an array?[a[0], a[1], a[2], ..., a[n-1]]?1 time results in the array?[a[n-1], a[0], a[1], a[2], ..., a[n-2]].Given the sorted rotated array?nums?of?unique?elements, return?the minimum element of this array.You must write an algorithm that runs in?O(log n) time.
區(qū)別就是154有重復(fù)值而153沒(méi)有。
跟昨天做的leetcode81一樣冕杠，我們可以用binary search微姊。不同的是81是要求和target比較。而這里是要找出最小值分预。
先上我的solution:
leetcode 153：
class Solution {
? ? public int findMin(int[] nums) {
? ? ? ? int left = 0, right = nums.length - 1;
? ? ? ? while(left < right) {
? ? ? ? ? ? int mid = left + (right - left)/2;
? ? ? ? ? ? if(nums[mid] < nums[right]) {
? ? ? ? ? ? ? ? right = mid;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? left = mid + 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return nums[left];
? ? }
}
leetcode 154：
class Solution {
? ? public int findMin(int[] nums) {
? ? ? ? int left = 0, right = nums.length -1;
? ? ? ? while(left<right) {
? ? ? ? ? ? while(left<right && nums[left] == nums[left+1]) {
? ? ? ? ? ? ? ? left ++;
? ? ? ? ? ? }
? ? ? ? ? ? while(left<right&& nums[right] == nums[right-1]) {
? ? ? ? ? ? ? ? right --;
? ? ? ? ? ? }
? ? ? ? ? ? if(left +1 == right) {
? ? ? ? ? ? ? ? return Math.min(nums[left], nums[right]);
? ? ? ? ? ? }
? ? ? ? ? ? if(left ==right){
? ? ? ? ? ? ? ? return nums[left];
? ? ? ? ? ? }
? ? ? ? ? ? int mid = left + (right - left) /2;
? ? ? ? ? ? // if (nums[left] == nums[mid] && nums[mid]== nums[right]){
? ? ? ? ? ? //? ? left += 1;
? ? ? ? ? ? //? ? right -= 1;
? ? ? ? ? ? // }
? ? ? ? ? ? if(nums[mid]<nums[right]) {
? ? ? ? ? ? ? ? right = mid;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? left = mid + 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return nums[left];
? ? }
}
有一部分我注釋掉的部分是另外一種解法兢交，比較簡(jiǎn)潔，可以不用去特殊處理Corner case笼痹。
這里記錄一下我解題的時(shí)候踩的坑配喳。
1. 為何返回的是nums[left]
ans: 因?yàn)槲覀円〉氖亲钚≈怠Ｎ覀兛偸勤呄蛴诎褏^(qū)間縮小到變成有序与倡，然后取值界逛。所以最后肯定是nums[left]<=nums[right].
如果題目變成取最大值，那肯定最后返回的是nums[right].
2. 為何一開(kāi)始循環(huán)條件是left<right 而不是left<=right.
ans: 考慮特殊情況纺座，一個(gè)值的時(shí)候息拜，我們是不希望進(jìn)入循環(huán)的，直接return净响。之前做target比較的時(shí)候少欺，solution在循環(huán)里面找target，所以就算一個(gè)值也要看一下馋贤，就是left<=right赞别。
3. 這道題的解法有一個(gè)比較有意思的，就是這里我們寫的是if(nums[mid] < nums[right])配乓， 而不是和nums[left]比較仿滔。如果寫和nums[left]比較，我們會(huì)跑不過(guò)犹芹，e.g test case?[4,5,6,7,0,1,2]. 為什么呢崎页？
ans: 因?yàn)槲覀円〉檬亲钚≈担琺id 和 left比的時(shí)候腰埂，不能知道最小值落在了哪一個(gè)部分飒焦。比如[0,1,2] mid > left, 最小值在mid左邊，比如[3,5,1,2], mid > left,? 最小值在mid右邊屿笼。但是和right比肯定能知道最小值在哪一個(gè)部分牺荠。
4. 關(guān)于去重，為什么不能直接想之前81題那樣直接兩邊去重然后比較驴一？
ans: 具體情況具體分析休雌，還沒(méi)有總結(jié)出規(guī)律，但是一個(gè)比較好的解題方法是肝断，請(qǐng)test corner case挑辆。比如[1], [1, 1], [1, 1 , 1]
另外發(fā)現(xiàn)一個(gè)東西：
leetcode的explore card of binary search例朱。這里對(duì)一些binary search的題目進(jìn)行了歸納總結(jié)，然后總結(jié)出一些模板鱼蝉。實(shí)在不行可以背一背洒嗤。
