导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二
    3. 方法三

LeetCode-153.Find Minimum in Rotated Sorted Array

题目

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.

翻译

假设一个有序数组,以一个未知的枢轴旋转了。(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2)。
找出数组中的最小元素。
你可以认为数组中没有重复元素。

方法一

遍历……

1
2
3
4
5
6
7
8
public class Solution {
public int findMin(int[] nums) {
for (int i = 1; i < nums.length; i++)
if (nums[i - 1] > nums[i])
return nums[i];
return nums[0];
}
}

方法二

二分变种
旋转后的数组分成左右两部分,以int last = nums[nums.length - 1]作为哨兵,比last大的都在左半部分,比last小的都在右半部分。
每次二分后将nums[mid]与last作比较,如果nums[mid] > last,则mid在左半部分,将low移到mid的右边;如果nums[mid] <= last,则mid在右半部分,将high移到mid的左边。
退出循环时,high指向最大值,low指向最小值:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1, last = nums[high];
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] > last) low = mid + 1;
else if (nums[mid] <= last) high = mid - 1;
}
return nums[low];
}
}

需要注意的是,以nums[nums.length - 1]作为哨兵,当数组旋转为初始递增状态时也适用;而以nums[0]作为哨兵时,当数组旋转为初始递增状态时则会出错,需要对这种情况,包括只有一个元素的情况先做判断:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
// 数组旋转出初始递增状态的情况,包括只有一个元素的情况
if (nums[low] <= nums[high]) return nums[low];
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] >= nums[0]) low = mid + 1;
else if (nums[mid] < nums[0]) high = mid - 1;
}
return nums[low];
}
}

方法三

方法二对情况的讨论不是很清晰,且无法应付154. Find Minimum in Rotated Sorted Array II。
看到参考二的文章,突然想起了之前做过的278. First Bad Version,其实两题有相同的地方:都是分成左右两部分,找右半部分的第一个元素。
改造了278题的算法如下:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1, last = nums[high];
while (low < high) {
int mid = (low + high) / 2;
if (nums[mid] > last) low = mid + 1;
else if(nums[mid] < last) high = mid;
}
return nums[high];
}
}

利用方法二,将last = nums[num.length - 1]作为哨兵,判断num[mid]在左半部分还是右半部分,相当于好版本或坏版本。
当mid在左半部分时,更新low为mid + 1,否则更新high为mid,最后返回nums[high]即可。
注意循环条件为low<high。

参考:
http://www.cnblogs.com/x1957/p/4028271.html
http://www.tuicool.com/articles/ry6Zz2