剑指Offer 面试题11旋转数组的最小数字

11旋转数组的最小数字

剑指Offer面试题汇总

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。 要求时间复杂度使用O(logN)

输入输出
示例1

输入：[3,4,5,1,2]
输出：1

示例2

输入：[2,2,2,0,1]
输出：0

解决方案
主要考验二分，使用O(logN)复杂度
设置两个指针
p1指向数组头
p2指向数组尾
mid指针指向两个指针的中间
mid>p2时，p1就右移，如果mid等于p1，p1++
mid<=p1时，p2就左移，如果mid等于p2，p2++

如果p1<p2说明不是旋转数组，直接返回p1的值
如果p1=mid=p2使用顺序查找O(n)

    public static int minArray(int[] numbers) {
        int p1 = 0;
        int p2 = numbers.length-1;
        int midP = (p1+p2)/2;
        //情况1：数组是顺序的
        if(numbers[p1]<numbers[p2]) return numbers[p1];
        //情况2：数组是1011111或者11111101的情况
        if(numbers[p1]==numbers[p2]&&numbers[p2]==numbers[midP]){
            int min = Integer.MAX_VALUE;
            for(int a:numbers){
                min = min<a?min:a;
            }
            return min;
        }
        //情况3：数组是二分查找
        while(p1<p2){
            if(numbers[midP]>numbers[p2]){
                p1 = midP==p1?++p1:midP;
            }else if(numbers[midP]<=numbers[p2]){
                p2 = midP==p2?++p2:midP;
            }
            midP = (p1+p2)/2;
        }
        return numbers[p1];
    }
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