剑指offer-旋转数组的最小数字

本文为剑指 offer 系列第八篇。
其实就是找有序数组的最小元素，只是这个有序数组进行了一次旋转而已。

题目描述

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

解题思路

思路1

直接使用stl中的min_element方法。一行代码就可以搞定。

思路2

思路2是可以使用类似于二分的方法进行查找，我们在看这个数字经过旋转之后的变化，其实如果一旦二分，我们会发现那个最小元素其实会存在于某个区间内，而这个区间并不满足左边的元素要小于右边的元素。而另一个区间是满足的，因为本身的数组就是非递减排序的，所以只会有一个区间是出现降序排列。这样我们只要找到导致降序的点即可。
还有一个要注意的点，就是这个里面可能会有重复数据，所以可能出现中间元素和尾元素相等的情况，这个时候其实不能确定那个降序点在什么地方，所以这个时候就尾节点区间减少一个即可。

解题代码

思路1代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        return *min_element(rotateArray.begin(),rotateArray.end());
    }
};

时间复杂度为O(n),空间复杂度为O(n)

思路2代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0) return 0;
        if(rotateArray.size() == 1) return rotateArray[0];
        int l = 0,r = rotateArray.size()-1;
        while(l<r){
            int mid = l + (r-l)/2;
            if(rotateArray[mid]<rotateArray[r]){
                r = mid;
            }else if(rotateArray[mid]>rotateArray[r]){
                l = mid+1;
            }else{
                r--;
            }
        }
        return rotateArray[l];
    }
};

时间复杂度好的情况为O(logn),不好的情况为O(n),空间复杂度为O(n)
以上，本题结束！