旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

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

题解

思路1

直接遍历

时间复杂度: O(N)- 空间复杂度: O(1)

思路2

二分查找

分析：旋转数组可以看成是两个有序数组组成的，最小元素就是这两个数组的分界点

用两个指针进行二分查找，lo指针总是指向第一个数组的终点，hi指针总是指向第二个数组的起点

直到 lo 与 hi相邻，即 lo == hi -1

时间复杂度: O(log (N))- 空间复杂度: O(1)

public int minNumberInRotateArray(int[] array) {
    if (array.length == 0)
        return 0;

    int lo = 0;
    int hi = array.length - 1;
    int m = (lo + hi) / 2;
    while (lo != hi - 1) {
        if (array[lo] <= array[m]) {
            lo = m;
            m = (lo + hi) / 2;
        }

        if (array[hi] >= array[m]) {
            hi = m;
            m = (lo + hi) / 2;
        }
    }
    return array[hi];
}

等等

这样写有缺陷

比如 {1，0，1，1，1} 和 {1，1，1，0，1} 这两个

如果中间指针 和 前后指针都相等的情况，找不出最小的

碰到这种情况只能顺序查找了

public int minNumberInRotateArray(int[] array) {
    if (array.length == 0)
        return 0;

    int lo = 0;
    int hi = array.length - 1;
    int m = (lo + hi) / 2;
    while (lo < hi - 1) {
        /*这种特殊情况，只能顺序查找*/
        if (array[lo] == array[hi] && array[lo] == array[m]) {
            int res = 0;
            for (int i = lo + 1; i < hi; i++) {
                if (res > array[i])
                    res = array[i];
            }
            return res;
        }

        if (array[lo] <= array[m]) {
            lo = m;
            m = (lo + hi) / 2;
        }

        if (array[hi] >= array[m]) {
            hi = m;
            m = (lo + hi) / 2;
        }
    }
    return array[hi];
}