LeetCode 153 Find Minimum in Rotated Sorted Array I
Suppose a sorted array 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.
You may assume no duplicate exists in the array.
对于sorted array直接考虑binary search。要分清楚情况,rotated sorted array存在一个很好的性质,就是:
不管pivot在哪里,开头的k个number,总是已经排好序的!!!
如:
[0,1,2,3,4,5,6,7]
[6,7,0,1,2,3,4,5]
[2,3,4,5,6,7,0,1]
可以看到对于rotated sorted array,只可能存在3种case!!!
1)nums[left] < nums[mid] && nums[mid] < nums[right]
2)nums[left] > nums[mid] && nums[mid] < nums[right]
3)nums[left] < nums[mid] && nums[mid] > nums[right]
而对于一般的array,还应该存在:
4)nums[left] > nums[mid] && nums[mid] > nums[right]
即完全的逆序(对于任何一个substring,都不可能满足):
[7,6,5,4,3,2,1,0]
因此判断的时候,也不用考虑这种情况,只需要考虑:
nums[mid]与nums[right]的关系即可!!!
这里要注意,与常规binarySearch找某一个元素不同,
当搜索左侧区间时,mid=right,而不是mid=right-1;
这是因为考虑到mid到达边界的时候!!!
===================================
代码:
public class Solution {
public int findMin(int[] nums) {
// Find the pivot and the number after the pivot is the minimum number?!
int n = nums.length;
int l = 0, r = n-1, mid = 0;
while (l < r) {
mid = l + (r-l) / 2;
if (nums[mid] > nums[r])
l = mid + 1;
else
r = mid;
}
return nums[l];
}
}
LeetCode 154 Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
若数组中存在duplicate,那么相比与上述的三种情况,又会出现一种:
[0,1,2,3,4,5,6,7]
[6,7,0,1,2,3,4,5]
[2,3,4,5,6,7,0,1]
[6,6,7,0,1,2,3,4,5,6,6] //即使存在duplicate,还是可以通过mid与两侧关系判断
[2,2,3,4,5,6,7,0,1,2,2] //即使存在duplicate,还是可以通过mid与两侧关系判断
[3,3,3,3,3,0,1,2,3] // 无法判断在哪侧
[3,0,1,2,3,3,3,3,3] // 无法判断在哪侧
即:
5)nums[mid]与nums[left]与nums[right]三者相同,因此无法确定到底pivot在左半侧还是右半侧。
解决方法
思路一:在判断nums[mid]与nums[right]前
1 先判断是否nums[mid]与nums[left]与nums[right]三者相同
2 若是,则再判断nums[mid-1]是否与nums[mid]相同
3 若是,则左半部分全都相同,pivot在右侧;反之,则pivot在左侧
4 若三者不同,则按照不存在duplicate的方法继续判断pivot位置
思路二:
比较tricky!!!
若三者相同,则将upper bound缩小,再确定缩小后的区间即可。
[3,3,3,3,3,0,1,2,3] // 无法判断在哪侧
[3,0,1,2,3,3,3,3,3] // 无法判断在哪侧
对于以上两种情况,由于nums[mid]=nums[right],因此right--,重新判断缩小后的区间,此时变为:
[3,3,3,3,3,0,1,2]
[3,0,1,2,3,3,3,3]
发现第一与第二种case,均可以判断出pivot!!!
代码:
public class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n-1, mid = 0;
while (l < r) {
mid = l + (r-l)/2;
if (nums[mid] > nums[r])
l = mid+1;
else if (nums[mid] < nums[r])
r = mid;
else
r--;
}
return nums[l];
}
}