05 August 2008
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.
You may assume no duplicate exists in the array.
Example 1:
1
2
Input: [3,4,5,1,2]
Output: 1
Example 2:
1
2
Input: [4,5,6,7,0,1,2]
Output: 0
一个已经升序排好的数组以某个轴rotated调转左右的元素，然后在调转后的array里寻找到最小的元素，数组里的元素是没有重复的。这道题凭空想的话不容易想到，拿原题中的例子 [0,1,2,4,5,6,7]转变成[4,5,6,7,0,1,2]来观察规律，如果最小值如果没有rotated，为nums[0]，如果rotated了，满足nums[min]<nums[min-1]，也就是说最小值比它之前的数值下（index大）；用Binary Search的找到中间的值nums[mid]，如果找到的值小于它左边的值，则该值就是最小值 - 因为原本是升序，只有在最小值处它才会小于左边的值，直接返回；如果nums[mid]大于左边的值，那么nums[mid]有可能是[4,5,6,7,0,1,2]或[6,7,0,1,2,4,5]这样的情况，1）nums[mid]大于左边的值也大于右边的值，说明最小值在该nums[mid]右边；2）nums[mid]大于左边的值但小于右边的值，说明最小值在该nums[mid]的左边。以此类推，直到找到一个nums[mid]小于它左边的值为止。
因为数组的元素没有重复，所以跟下一道相比是简单了很多。
Time： O(logn)； Space：O(1).
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return Integer.MIN_VALUE;
}
int left = 0, right = nums.length - 1;
if (nums[left] < nums[right]) { // 先判断是不是全局有序
return nums[left];
}
// 二分法确定最小值在左边还是右边
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[left]) {
left = mid;
} else {
right = mid;
}
}
return Math.min(nums[left], nums[right]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int right = nums.length - 1;
if (nums[left] < nums[right]) {
return nums[left];
}
while (left + 1 < right) {
int mid = left + (right - left) / 2;
// if (mid > 0 && nums[mid] < nums[mid - 1]) {
// return nums[mid];
// }
// if (mid < nums.length - 1 && nums[mid] > nums[mid + 1]) {
// return nums[mid + 1];
// }
if (nums[mid] > nums[left]) {
left = mid;
} else {
right = mid;
}
}
// return nums[right] < nums[left] ? nums[right] : nums[left]; //模板
return nums[right]; // left和right停在下降的地方
}
}