29
03/2015
[LeetCode]Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
解题思路：
最开始不明白旋转数组是何物，最初的想法就是逐个元素扫描，找到一个最小的值，代码如下：
class Solution {
public:
int findMin(vector<int> &num) {
int len = num.size();
int minNumber = num[0];
for(int i=1; i<len; i++){
if(num[i]<minNumber){
minNumber = num[i];
}
}
return minNumber;
}
};时间复杂度为O（n），leetcode也AC了，而且执行速度很快，只需要7ms。但LeetCode不会出这么容易的问题吧？问题肯定在旋转数组上了，于是乎，查找相关网页如下http://blog.csdn.net/lalor/article/details/7961323，里头的旋转代码非常经典。弄清楚旋转数组是什么之后，我们利用旋转数组部分有序的情况，得到下面的代码：
class Solution {
public:
int findMin(vector<int> &num) {
int len = num.size();
int min = 0;
int max = len - 1;
int middle = (min + max) / 2;
while(true){
//判断边界
if(min==max){
return num[min];
}
if(min + 1 == max){
if(num[min]<num[max]){
return num[min];
}else{
return num[max];
}
}
if(num[middle]<num[max]){
max=middle;
}else{
min = middle;
}
middle = (max + min) / 2;
}
}
};这里每次去除一半的查询空间，类似于二分查找，故其时间复杂度为O(logn)。
0 条评论