Leetcode Find Minimum in Rotated Sorted Array 题解

Leetcode Find Minimum in Rotated Sorted Array 题解

Leetcode Find Minimum in Rotated Sorted Array

题目大意：

     对一个有序数组翻转， 就是随机取前K个数，移动到数组的后面，然后让你找出最小的那个数，注意，K有可能是0，也就是没有翻转。

     毫无疑问，遍历一次肯定可以找到，但这样时间复杂度是O(n)，如果你在面试的时候遇到这样的问题，你这样回答面试官肯定不会满意的，我们接下来讨论有没有什么更快的方法。O(nlogn)??

我还是把O(N)的代码贴出来，不知道为什么leetcode上居然不超时。

//O(n)
class Solution {
public:
    int findMin(vector<int> &num) {
        int minval = 0x3f3f3f3f;
        int len = num.size();
        for (int i = 0; i < len; i++) {
            minval = min(minval, num[i]);
        }
        return minval;
    }
};

       既然数字开始是有序的，我们第一个应该想到的方法就是二分，事实上就是可以二分。 如果进行的翻转，肯定会变成两部分有序数组，第一部分的任何一个数都大于第二部分的，第二部分中最后一个数肯定是最大的。这样二分的判断条件就是，只要mid位置的值大于最后一个数，肯定能确定mid在第一部分中，然后往右二分即可，反之往左。 

       我本人写了两次代码，第一份很不尽人意，首先对没有翻转的情况做了特判，然后一直遇到二分边界的问题，只要二分两个数的时候就会死循环，索性就加了特判，两个数的时候直接输出最小的一个，代码冗长混乱，思路也不严谨，先贴出来做个反例。

//O(nlogn) bad
class Solution {
public:
    int findMin(vector<int> &num) {
        int len = num.size();
        if (num[0] <= num[len-1])
            return num[0];
        int l = 0, r = len-1;
        while (l < r) {
            int mid = (l+r)>>1;
            if (num[mid] > num[l]) {
                if (num[mid] > num[0])
                    l = mid+1;
                if (num[mid] < num[len-1])
                    r = mid;
            }
            else if (num[mid] < num[r])
                r = mid;
            else 
                return min(num[l], num[r]);
        }
        return num[l];
    }
};

接下来就是修改后的精简代码，其实不需要特判，重新写了二分的判断条件，然后代码瞬间短了好多，也易于理解。

//O(nlogn) good 
class Solution {
public:
    int findMin(vector<int> &num) {
        int len = num.size();
        int l = 0, r = len-1;
        while (l < r) {
            int mid = (l+r)>>1;
            if (num[mid] > num[r])
                l = mid+1;
            else 
                r = mid;
        }
        return num[l];
    }
};