題目描述

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。
輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。
例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。
NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。

解題思路一

最簡單粗暴的方法，窮舉出最小值，使得題意無意義，pass

public int minNumberInRotateArray(int[] array) {
    if (array == null || array.length == 0)
        return 0;
    else {
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }
}

解題思路二

對思路一進行優(yōu)化，進行旋轉(zhuǎn)后，數(shù)組最小值小于前一位

public int minNumberInRotateArray2(int[] array) {
    if (array == null || array.length == 0)
        return 0;
    else {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1])
                return array[i];
        }
        return array[0];  //數(shù)組值相同
    }
}

解題思路三

用類似二分查找的方法，不停收斂查找范圍。

參考?？徒忸}https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba?answerType=1&f=discussion

807319133_1566217781994_E0D8DA4D79E73A35EB4365215E2F13BB.png

public int minNumberInRotateArray3(int[] array) {
    if (array == null || array.length == 0) {
        return 0;
    } else {
        int left = 0;  //范圍的左邊界
        int right = array.length - 1; //范圍的右邊界，由提意可得左部分>=右部分
        int middle;
        while (left < right) {
            if (array[left] < array[right])  //考慮到特殊情況10111
                return array[left];
            middle = (left + right) / 2;//取中間
            if (array[left] < array[middle]) {
                //證明[left...middle]區(qū)間仍在左部分，直接left右移到middle+1
                left = middle + 1;
            }else if(array[middle] < array[right]){
                //證明[middle.....right]區(qū)間在右部分，直接right左移到middle，而不是middle處，middle處可能是最小值
                right = middle;
            }else{
                //無法判斷是在哪個部分，縮小區(qū)域
                left ++;
            }
        }
        return array[left];
    }
}