劍指offer面試題[8]-旋轉數組的最小數字

題目描述

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

牛客網上給的函數接口： class Solution {

public:

    int minNumberInRotateArray(vector<int> rotateArray) {

} }

分析：        看到題目的第一刻，我想的是既然這個數組原本是非遞減排序的，那麼在其旋轉後，就分為了兩個非遞減的子序列，第一個子序列的值一定是大于或等于第二個子序列的，那麼我們可以從第一進制素開始往後周遊，隻要前面的元素比它後面的一個元素大，說明第一個子序列的最後一個元素和第二個子序列的第一個元素相遇了，那麼明顯目前元素後面的那個元素就是最小元素了。當然還要判斷若數組元素是否為空。        于是我開始動手寫程式，如下：  class Solution {

 public:

    int minNumberInRotateArray(vector<int> rotateArray) {         int n=rotateArray.size( );

        if(n==0)

              return 0;

        for(int i=0;i<n-1;i++)

          {

              if(rotateArray[i]>rotateArray[i+1])

                  return  rotateArray[i+1];

          }

        return  rotateArray[0];

} }        很神奇的是竟然通過了，我很興奮，但是總覺得劍指offer上的題考慮的遠遠不止這，于是我打開課本，果然我很low，考慮的問題太少，複雜度是O(n)就不說，有的測試用例也沒想到。              書上寫的是利用 二分查找的思想（複雜度為O(logn）） 來解決這個問題，因為前面說過對于一個旋轉的數組來說，旋轉後數組實際上分成了兩個排序的子數組，而且前面的子數組的元素均大于後面子數組的元素。而且最小的元素剛好是兩個子數組的分界。        對于一個長度為n的數組，設定兩個指針index1和index2，開始時index1指向第一個數組元素，即下标為0的位置，index2指向數組最後一個元素，及下标為n-1的位置。如果第一個元素大于最後一個元素，說明旋轉了0個元素，輸出第一個元素（最小）。否則找到數組中間位置indexMid的元素。indexMid=（index1+index2）/2。如果indexMid位置對應的值大于index1對應的值，那麼說明indexMid位置對應的值位于第一個子數組中，最小值應該在indexMid後面，是以将indexMid賦給index1。如果indexMid位置對應的值小于index2對應的值，那麼說明indexMid位置對應的值位于第二個子數組中，最小值應該在indexMid前面，是以将indexMid賦給index2。直到index1和index2的值相差1，即index1指向第一個子數組的最後一個位置，index2指向第二個子數組的第一個位置。讀者可以自己以數組{3,4,5,1,2}分析。         于是有代碼：(紅色代碼部分說明見最下面) class Solution {

public:

    int minNumberInRotateArray(vector<int> rotateArray) {

        int n=rotateArray.size( );

        if(n==0)

           return 0;

        int index1=0;

        int index2=n-1;

        int indexMid=index1;   

        while(rotateArray[index1]>=rotateArray[index2])

          {

             if(index2-index1==1)    //注意不要搞反了減數和被減數

                 {

                    indexMid=index2;

                    break;

                 }   

             indexMid=(index1+index2)/2;

             //如果出現了下标index1、index2及indexMid三個值相等的情況，那麼就隻能是順序查找了

             if(rotateArray[indexMid]==rotateArray[index1]&&rotateArray[index1]==rotateArray[index2])

                 {

                    return MinInOrder(rotateArray,index1,index2);

                 }

             if(rotateArray[indexMid]>=rotateArray[index1])

                    index1=indexMid;

             else if(rotateArray[indexMid]<=rotateArray[index2])

                    index2=indexMid;

          }

        return rotateArray[indexMid];

    }        int MinInOrder(vector<int> rotateArray,int index1,int index2)     //注意函數定義的位置，不要在函數minNumberInRotateArray内定義

           {

              int Min=rotateArray[index1];

              for(int i=index1+1;i<=index2;i++)

                 { if(Min>rotateArray[i])

                      Min=rotateArray[i];

                 }

              return Min;

           }

};

       我們沒有考慮到的一種情況是：如果index1、index2及indexMid對應的值相等怎麼辦？        比如數組{1,0,1,1,1}和數組{1,1,1,0,1}都是原始非遞減數組{0,1,1,1,1}的旋轉數組。可以看到第一個元素、第三個元素以及第五個元素的值都是1，此時， 我們不得不采用順序查找的方法 。