旋轉數組的最小值

1 基本思路：旋轉數組的特點：旋轉數組隻有在旋轉的接口處（旋轉前數組的最後一個元素和旋轉前數組的第一個元素拼接的地方）會出現下降，其餘大部分都是非遞減的。利用這個特點，隻要找到旋轉數組中第一個比前一個元素小的元素，該元素就是旋轉前數組的第一個元素，因為旋轉前數組時非遞減的，是以該元素即為數組中最小元素。這是一般情況。

還需要考慮兩個特殊情況：第一個是比較正常的特殊情況，就是數組長度為0的時候，傳回值為0；第二個是由于旋轉前數組時非遞減的，是以數組中的元素可能全部相等，此時傳回數組中任意一個元素即可。

2 具體代碼

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        //如果旋轉數組長度為0
        if(rotateArray.size()==0)
            return 0;
        
        //如果旋轉數組中的元素全相等，傳回數組任意一個元素即可
        bool isAllEqual=true;
        for(int i=0;i<rotateArray.size()-1;i++)
        {
         if(rotateArray[i]!=rotateArray[i+1])
         {
              isAllEqual=false;
              break;
         }
        }
         if(isAllEqual)
             return rotateArray[0];
         //如果旋轉數組中的元素不全相等，傳回第一個比前一個元素小的元素即可
        for(int i=0;i<rotateArray.size()-1;i++)
        {
            if(rotateArray[i+1]<rotateArray[i])
                 return rotateArray[i+1];
        }
    }
};
           

報錯：

原因：有些編譯器因為所有的傳回值都在條件語句中，是以報錯。調整一下程式結構，使得至少一個傳回值不在條件語句中。

調整代碼：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        //如果旋轉數組長度為0
        if(rotateArray.size()!=0)
        {
        //如果旋轉數組中的元素全相等，傳回數組任意一個元素即可
        bool isAllEqual=true;
        for(int i=0;i<rotateArray.size()-1;i++)
        {
         if(rotateArray[i]!=rotateArray[i+1])
         {
              isAllEqual=false;
              break;
         }
        }
         if(isAllEqual)
             return rotateArray[0];
         //如果旋轉數組中的元素不全相等，傳回第一個比前一個元素小的元素即可
        for(int i=0;i<rotateArray.size()-1;i++)
        {
            if(rotateArray[i+1]<rotateArray[i])
                 return rotateArray[i+1];
        }
    }
        return 0;
    }
};
           

運作正确。

補充說明：這裡有一種特殊情況，應為處理方式相同，所有隐藏在了代碼裡面，但是不代表不需要考慮。

看到程式中的for循環中i的取值是從0到rotateArray.size()-1，左閉右開。當rotateArray.size()==1時（即rotateArray中隻有一個元素），這個循環會一次都不執行。由于用于判斷數組中全部元素相等的标志變量isAllEqual預設為true，因為沒有執行循環，isAllEqual最終仍為true，這和實際情況中的結果是一緻的：即數組隻有一個元素時，數組中全部元素相等，是以這種特殊情況可以歸在普通情況的代碼中。

3 收獲：

一般報錯 control may reach end of non-void function是因為函數的所有傳回值均在條件語句中，這時候隻需要調整一個return語句不在條件語句中，既可編譯通過。