xindoo is
always here

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];
    }
};
打赏
未经允许不得转载:XINDOO » Leetcode Find Minimum in Rotated Sorted Array 题解
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏