【LeetCode】Find Minimum in Rotated Sorted Array 在旋转数组中找最小数

Add Date 2014-10-15

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.

这个很简单,因为没有重复数字,数组本质上还是有序的,用类似二分查找的方法复杂度O(log n)。记得考虑一下整个数组没有 rotated 的情况。

20号又加了有重复数字的题II,直接附II的 code 吧,II中需要考虑前中后三个数相等的情况,此时无法确定最小值在哪边,只能遍历一遍。

 class Solution {
public:
int findMinN(vector<int> &num, int min, int max) {
int minN = num[min];
for(int i = min+; i <= max; ++i) {
if(num[i] < minN)
minN = num[i];
}
return minN;
}
int findMin(vector<int> &num, int min, int max) {
if(min == max || num[min] < num[max])
return num[min];
int mid = (max+min)>>;
if(num[mid] < num[min]) {
return findMin(num, min, mid);
}
else if(num[mid] > num[max]) {
return findMin(num, mid+, max);
}
else
return findMinN(num, min, max);
}
int findMin(vector<int> &num) {
int len = num.size();
return findMin(num, , len-);
}
};
上一篇:如何删除win8自带输入法


下一篇:kendo-ui的使用和开发自己的组件