By

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

题目解析

非递减排序的数组进行旋转之后，会变成两个非递减数组的组合，例如1 2 2 3 4 5，旋转变成了2 3 4 5 1 2，第一种解法就是遍历数组直到发现数组中的元素小于前一个元素，该元素就是最小元素，时间复杂度为O(n)。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int size = rotateArray.size();
        //数组长度为0
        if(!size) return 0;
        
        //数组部分旋转
        for(int i=0;i<size-1;i++){
            if(rotateArray[i]>rotateArray[i+1]){
                return rotateArray[i+1];
            }
        }
        
        //数组完全旋转
        return rotateArray[0];
    }
};

第二种解法就是简单的二分查找的变形，旋转数组具有一定程度的顺序，最小元素是两个非递减数组的边界元素，且第一个非递减数组的大小不小于第二个非递减数组。如1 2 2 3 4 5，旋转为2 3 4 5 1 2，第一个非递减数组为2 3 4 5，第二个非递减数组为1 2，最小元素即使第二个递减数组的第一个元素1。
若以mid为下标的元素的前一个元素大于它，则最小元素就是它；或者它的后一个元素小于它，则最小元素就是后一个元素。否则进行二分查找，以mid为下标的元素大于以low为下标的元素，说明最小元素在后半部分，令low=mid+1。反之，若mid下标的元素小于以low为下标的元素，说明最小元素在前半部分，令high=mid-1。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int size = rotateArray.size();
        //数组长度为0
        if(!size) return 0;
        
        //数组完全旋转
        if(rotateArray[0]<rotateArray[size-1])
            return rotateArray[0];

        //数组部分旋转
        int low=0,high=size-1,mid=0;
        while(low<=high){
            mid=(low+high)/2;
            if(rotateArray[mid]<rotateArray[mid-1])
                return rotateArray[mid];
            if(rotateArray[mid]>rotateArray[mid+1])
                return rotateArray[mid+1];
            if(rotateArray[mid]>rotateArray[low])
                low=mid+1;
            else if(rotateArray[mid]<=rotateArray[low])
                high=mid-1;
        }
        return 0;
    }
};