旋转数组中的最小数字

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 1.7k | 阅读时长 ≈ 2 分钟

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。


NOTE：给出的所有元素都大于0，若数组大小为0，请返回0：

解析：

采用二分法解答这个问题，
　　mid = low + (high - low)/2

需要考虑三种情况：
(1)array[mid] > array[high]:
　　出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。

　　low = mid + 1

(2)array[mid] == array[high]:
　　出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边还是右边,这时只好一个一个试 ，

　　high = high - 1

(3)array[mid] < array[high]:
　　出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左边。因为右边必然都是递增的。

　　high = mid

注意这里有个坑（坑1）：如果待查询的范围最后只剩两个数(即最后一次迭代循环)，那么mid 一定会指向下标靠前的数字：

　　比如 array = [4,6]
　　array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;

　　如果high = mid - 1，就会产生错误， 因此high = mid
　　但情形(1)中low = mid + 1就不会错误

考虑临界情况：(最后一次迭代循环)

情形1：[max,min]时，array[mid]–>max，而array[high]–>min，此时满足if条件：array[mid]> array[high]，将执行low=mid+1；然后只剩余一个元素：array[low=mid=high]=min，跳出while循环返回array[low]或array[high]即可。

情形2：[min,max]时，array[mid]–>min，而array[high]–>min，此时满足if条件：array[mid]< array[high]，将执行high=mid；然后只剩余一个元素：array[low=mid=high]=min，跳出while循环返回array[low]或array[high]即可。

综合1、2，即将最后一个元素锁定到min即可，即设法当跳出循环时使其满足array[low=high]=min

代码：（二分查找的迭代形式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int low = 0 ; int high = array.length - 1;   
        while(low < high){
            int mid = (low + high)/2;        
            if(array[mid] > array[high])
               //这里mid必须+1，否则面对剩余两个元素：[max,min]情况时会陷入无限循环
               low = mid + 1; //由坑1导致的-->坑2
            else if(array[mid] == array[high])
                high = high - 1;
            else
                high = mid;
        }
        return array[low];
    }
}
---------------- The End ----------------
0%