05 August 2008
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 1
[0,1,2,4,5,6,7]
1
[4,5,6,7,0,1,2]
Find the minimum element.
The array may contain duplicates.
Example 1:
1
2
Input: [1,3,5]
Output: 1
Example 2:
1
2
Input: [2,2,2,0,1]
Output: 0
Note:
这道题跟上一道题基本一样，区别就是数组本身里面可以有重复元素了。依然用Binary Search，只比较右边的指针即可， 例如原本的数组是[0,1,2,2,2,3]，如果rotate后的数组是[2,2,3,0,1,2]，nums[mid]大于nums[right]，可以确定最小的数在右边；如果是rotate后的数组是[3,0,1,2,2,2]，nums[mid]小于nums[right]，确定最小数在左边或就是nums[mid]自己；如果二者相等，无法确定最小数的位置，这时候可以把右标-1，缩小范围。最后判断条件结束left>=right的时候，这个时候条件停止，left总是指向最后一个数也就是最小数。
Time：这个不是常规的Binary Search，如果一直中间数等于右指针的数，那么最坏情况是O(n)； Space：O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left)/2;
if (nums[mid] > nums[right]) {//中间数大于右指针的数，说明最小数在右边
left = mid + 1;
} else if (nums[mid] < nums[right]) {//中间数小于右边的数，最小数在左边，注意这里中间数有可能是最小数，所以不要mid-1
right = mid;
} else {//如果中间数等于右边的数，则无法知道最小数在哪边，但这时候可以把右标往左移进行比较
right--;
}
}
return nums[left];
}
}