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.
区别就是154有重复值而153没有。
跟昨天做的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];
}
}
有一部分我注释掉的部分是另外一种解法，比较简洁，可以不用去特殊处理Corner case。
这里记录一下我解题的时候踩的坑。
1. 为何返回的是nums[left]
ans: 因为我们要取的是最小值。我们总是趋向于把区间缩小到变成有序，然后取值。所以最后肯定是nums[left]<=nums[right].
如果题目变成取最大值，那肯定最后返回的是nums[right].
2. 为何一开始循环条件是left<right 而不是left<=right.
ans: 考虑特殊情况，一个值的时候，我们是不希望进入循环的，直接return。之前做target比较的时候，solution在循环里面找target，所以就算一个值也要看一下，就是left<=right。
3. 这道题的解法有一个比较有意思的，就是这里我们写的是if(nums[mid] < nums[right])， 而不是和nums[left]比较。如果写和nums[left]比较，我们会跑不过，e.g test case [4,5,6,7,0,1,2]. 为什么呢？
ans: 因为我们要取得是最小值，mid 和 left比的时候，不能知道最小值落在了哪一个部分。比如[0,1,2] mid > left, 最小值在mid左边，比如[3,5,1,2], mid > left, 最小值在mid右边。但是和right比肯定能知道最小值在哪一个部分。
4. 关于去重，为什么不能直接想之前81题那样直接两边去重然后比较？
ans: 具体情况具体分析，还没有总结出规律，但是一个比较好的解题方法是，请test corner case。比如[1], [1, 1], [1, 1 , 1]
另外发现一个东西：
leetcode的explore card of binary search。这里对一些binary search的题目进行了归纳总结，然后总结出一些模板。实在不行可以背一背。
