有题目可以知道找的是数组中的最小值,最容易想到的方法应该就是直接遍历数组,使用一个变量保存数组中的最小值
class Solution {
public int minArray(int[] numbers) {
if(numbers.length == 0) return 0;
int res = numbers[0];
for(int i : numbers) res = Math.min(res, i);
return res;
}
}
上述的这种做法的时间复杂度是线性,即O(n)的。
优化
由于题目中初始的数组是递增的数组,然后再某一个位置旋转了,使得数组前面的数到后面了
class Solution {
public int minArray(int[] numbers) {
int l = 0, r = numbers.length - 1;
while(r > 0 && numbers[r] == numbers[l]) r --;
//下面成立说明了剩下的序列就是有序的(这句话也可以不加,但是后面的基准点就不能选错了)
if(numbers[l] < numbers[r]) return numbers[0];
int x = numbers[r];
while(l < r){
int mid = l + r >> 1;
if(numbers[mid] <= x) r = mid;
else l = mid + 1;
}
return numbers[l];
}
}
上述的算法平均时间复杂度为O(logn),在最坏的情况下为O(n)
原文:https://www.cnblogs.com/Lngstart/p/14717608.html