题目:
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,
0 1 2 4 5 6 7
might become4 5 6 7 0 1 2
).Find the minimum element.
The array may contain duplicates.
分析:
一个升序数组(可能有重复元素),所有元素旋转n个位置,例如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]。但是你不知道n是多少。请找出旋转后的数组中的最小元素。
下面给出一个二分查找的解法。在数列中,最小的数有一个特征:该数左侧的所有数都大于等于右侧的数,并且左侧和右侧的数都分别是递增的。开始,使用2个指针l,r指向数组的两端。根据刚才提到的特征,为了使l和r不断逼近最小的数,l应当尽可能指向更大的数,r应当尽可能指向更小的数。比较r和中间的数m。如果m较小,则r指向m;如果r较小,则l指向m+1。由于数组中可能出现相同的元素,如果m和r相等怎么办?只要把r左移一位再继续查找即可。
另外说明一下,取中间数的时候为什么用 m = l + (r – l) / 2 而不是 m = (l + r) / 2。如果数组的长度太大,以至于大于等于int的上界,l + r可能会引起溢出而变成负数。所以我们分成2步,先做减法,再做加法,防止溢出。
代码:
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public class Solution { public int findMin(int[] nums) { int l = 0; int r = nums.length - 1; while(l < r){ int m = l + (r - l) / 2; if(nums[m] > nums[r]) l = m + 1; else if (nums[m] < nums[r]) r = m; else r--; } return nums[l]; } } |