题目:
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.
You may assume no duplicate exists in the array.
解题思路:
首先假设一个sorted没有rotated的数组[1,2,3],假设我们通过一个pivot把这个数组rotate,那么结果可能为:[2,3,1], [3,1,2], 可以发现:num[low]永远大于(或等于)num[high]。因为你之前是sorted的数组,你在一个sorted的数组找了一个pivot进行rotate,那么比如pivot后面的值都大于pivot之前的值。所以依据这个发现,以及二分法查找。我们可以根据以下判断来解题。num[mid]有两种可能性,如果num[mid] > num[high],证明num[mid]在rotated后的那个区间内,这个区间我们刚才已知都大于pivot之前的值,所以最小值就在low=mid+1那个区间内。另一种可能,num[mid] <= num[high],那么我们刚才可以看出来这种可能性说明mid~high以及是排好序的,那么最小值在high=mid这个区间内(mid可能是最小值)。依据此判断可以找到最小值。
代码如下:
1publicintfindMin(int[]num){
2intlow=0,high=num.length-1;
3while(low<high&&num[low]>=num[high]){
4intmid=(low+high)/2;
5if(num[mid]>num[high])
6low=mid+1;
7else
8high=mid;
9}
10returnnum[low];
11}
如果觉得《Find Minimum in Rotated Sorted Array leetcode java》对你有帮助,请点赞、收藏,并留下你的观点哦!