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 &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) badclass Solution {public: int findMin(vector &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 &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]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。