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

发表于 | 分类于

题目描述

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

解题思路

最笨的方法

一轮遍历查找，算法复杂度为O(n)，这样肯定找不到工作。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0) return 0;
        int min_num = rotateArray[0];
        for(int i=0; i<rotateArray.size(); i++){
            if(min_num > rotateArray[i])
                min_num = rotateArray[i];
        }
        return min_num;
    }
}

调用sort函数

这个我还真没想到，不过面试的时候，面试官肯定不会希望出现这种答案，笔试倒是可以这么写。

1
2
3
4
5
6
7
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        sort(rotateArray.begin(), rotateArray.end());
        return rotateArray[0];
    }
}

二分查找

因为这题之前做过，所以有印象。与二分查找的思想类似，不进行赘述。但是在做的时候遇到了超时的情况，原因是自己在更新low变量时写成了low=mid，这样会导致每次得到的新数组中总有一个大的数，因此不正确；相反的，high之所以等于mid，是因为mid数可能就是最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int low = 0, high = rotateArray.size()-1;
        return minNumber(rotateArray, low, high); 
    }
    int minNumber(vector<int> rotateArray, int low, int high){
        int mid = (low+high)/2;
        while(low != high){
            if(rotateArray[mid] <= rotateArray[high])
                high = mid;
            else low = mid+1;
            mid = (low+high) / 2;
        }
        return rotateArray[mid];
    }
};