劍指offer之旋轉(zhuǎn)數(shù)組的最小數(shù)字

歡迎關(guān)注作者簡書
csdn傳送門

題目

??把一個數(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。
??如果直接遍歷數(shù)組，時間復(fù)雜度為O（n）,可以利用旋轉(zhuǎn)數(shù)組的特性來解決此題；
思路：
（1）如果發(fā)生旋轉(zhuǎn)，前面的數(shù)至少去了一個放在數(shù)組的后面；

• 旋轉(zhuǎn)后，數(shù)組分為兩個排序數(shù)組，而且前一個數(shù)組中的數(shù)均大于等于后一個數(shù)組中的數(shù)，因為要查找數(shù)組中的最小數(shù)，也就是第二個數(shù)組中的第一個數(shù)，可以采用二分查找的思想；
• 設(shè)置兩個指針p1,p2，p1指向數(shù)組的開始位置，也就是第一個數(shù)組的開始位置，p2指向數(shù)組的終止位置，也就是第二個數(shù)組的結(jié)束位置。Mid=p1+p2/2;
• 如果中間位置mid的數(shù)大于p1指向的數(shù)，則mid在第一個數(shù)組中，讓p1指向mid所指向的數(shù)，p1指向的依然是數(shù)組1的數(shù)；
• 如果中間位置mid的數(shù)小于p2所指向的位置，則mid在第二個數(shù)組中，p2指向mid指向的數(shù)，p2指向的依然是數(shù)組2的數(shù)；
• Mid不是指向數(shù)組1的數(shù)，就是指向數(shù)組2的數(shù)，指向數(shù)組1的數(shù)，就讓p1移動到mid的位置，指向數(shù)組2就讓p2數(shù)組移動到mid的位置；直到p2移動到數(shù)組1的結(jié)束的位置，p1移動到數(shù)組2的開始的位置，此時p2與p1挨著，而且p1所指向的數(shù)組2的起始位置中存放的就是最小數(shù)；

（2）如果中間位置的數(shù)既等于p1位置數(shù)，又等于p2位置的數(shù)，這時候，不能確定移哪個指針，就必須采用順序查找的方法來尋找最小數(shù)；
總結(jié)：此題就是利用兩個指針，一個往后移，一個往前移，具體怎么移，通過mid的大小控制；直到兩個指針的位置挨著，就可以找到最小數(shù)了!
還需要考慮：
??如果數(shù)組取0個放在了數(shù)組的后面，也就是排序數(shù)組沒有變，這時p1指向的數(shù)小于p2指向的數(shù)；直接是數(shù)組的首元素是最小的數(shù)；

源碼

public class Solution{

    public int minNumberInRotateArray(int[] array){
        
        if(array == null){
            return 0;
        }

        int p1 = 0; // 從前往后走
        int p2 = array.length-1; // 從后往前走
        int min = array[p1]; // 如果沒發(fā)生旋轉(zhuǎn)，直接將array[0]的值返回
        int mid = 0;

        // 當數(shù)組旋轉(zhuǎn)了
        while(array[p1] > array[p2]){

            // 當兩個指針走到挨著的位置時，p2就是最小數(shù)了
            if(p2 - p1 == 1){
                min = array[p2];
                break;
            }

            mid = (p1 + p2)/2;
            // 如果中間位置的數(shù)既等于p1位置的數(shù)又等于p2位置的數(shù),只能使用順序查找
            // 1233455
            if(array[p1] == array[mid] && array[p2] == array[mid]){
                min = minInOrder(arr, p1, p2);
            }
            
            if(array[p1] <= array[mid]){
                p1 = mid;
            }else if(array[p2] >= array[mid]){
                p2 = mid;
            }
        }
        return min;
    }

    private int minInOrder(int[] array, int p1, int p2){
        int min = array[p1];
        for(int i = p1+1; i <= p2; i++){
            if(min > array[i]){
                min = array[i];
            }
        }
        return min;
    }
}

歡迎加入Java猿社區(qū)

歡迎加入Java猿社區(qū).png