leetcode 154. 尋找旋轉排序數組中的最小值 II  hard         

題目描述：

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

請找出其中最小的元素。

注意數組中可能存在重複的元素。

示例 1：

輸入: [1,3,5]

輸出: 1

示例 2：

輸入: [2,2,2,0,1]

輸出: 0

題目1 尋找旋轉排序數組中的最小值

解題思路：

跟上一題有點不同，因為可能存在重複元素。

是以我們首先需要把最後水準的一段删除，并且還有邊界情況，并且還有處理數組完全單調的特殊情況。

時間複雜度分析：二分的時間複雜度是 O(logn)，删除最後水準一段的時間複雜度最壞是 O(n)，是以總時間複雜度是 O(n)。

代碼：

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty())
            return -1;
        if(nums.size()==1)
            return nums[0];
        
        
        int left=0,right=nums.size()-1;
        //删除最後水準一段的時間複雜度最壞是 O(n)
        while(left<right && nums[right]==nums[left])
            --right;
        
        //為了避免處理邊界情況，我們在數組長度小于5時直接線性掃描出最小值。
        if(right-left+1<5){
            int res=INT_MAX;
            for(int i=left;i<=right;++i)
                res=min(res,nums[i]);
            return res;
        }
        
        // 沒有旋轉的情況
        if(nums[left]<=nums[right])
            return nums[left];
        // 一般情況
        int end=nums[right];
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<=end)
                right=mid;
            else
                left=mid+1;
        }
        
        return nums[left];
        
        
    }
};