题目六：旋转数组中的最小数组

 

 

 

特殊情况示例如下：

 如果出现这种情况，此时我们需要选择顺序排序：

 if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid])
            {
                return Minorder(rotateArray,left,right);
            }

    int Minorder(vector<int> &rotateArray, int left, int right)
    {
        int minVal = rotateArray[left];
        for(int i = left; i <= right; i )
        {
            minVal = min(minVal,rotateArray[i]);
        }
        return minVal;
    }

 

 

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) 
    {
        /*
        直接采用的排序 时间复杂度为o（n）
        sort(rotateArray.begin(),rotateArray.end());
        return rotateArray[0];
        */
        
        //模仿二分查找的算法，时间复杂度o（logn）
        if(rotateArray.empty())
        {
            return 0;
        }
        int left = 0;
        int right = rotateArray.size() - 1;
        int mid = 0; //针对的是把0个元素旋转到后面，那么第一个元素就是最小的数字
        //确保是一个旋转数组,首元素大于最后一个元素
        while(rotateArray[left] >= rotateArray[right])
        {
            if(right - left == 1)
            {
                mid = right;
                break;
            }
            mid = left   (right-left)/2;
            
            if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid])
            {
                return Minorder(rotateArray,left,right);
            }
            if(rotateArray[left] <= rotateArray[mid])
			{
                left = mid;
			}
			else if(rotateArray[right] >= rotateArray[mid])
			{
				right = mid;
			}
        }
        return rotateArray[mid];
    }
    
    int Minorder(vector<int> &rotateArray, int left, int right)
    {
        int minVal = rotateArray[left];
        for(int i = left; i <= right; i  )
        {
            minVal = min(minVal,rotateArray[i]);
        }
        return minVal;
    }
};

 

来源：http://www./content-4-192701.html