class Solution {
public int findMin(int[] nums) {
if(nums.length == 0) {
return -1;
}
Integer num = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; i++) {
num = Math.min(nums[i],num);
}
return num;
}
}
1.因为根据数组中数据状况的不同,所以对坏情况可能是O(n)
2,用上面的方法最简单,但是缺点在于必须遍历所有值
class Solution {
public int findMin(int[] nums) {
if(nums.length == 0) {
return -1;
}
int n = nums.length - 1;
while(n >= 0 && nums[n] == nums[0]) n--;
if(n == -1) return nums[0];
if(nums[n] >= nums[0]) return nums[0];
int l = 0;
int r = n;
while(l < r) {
int mid = l + r >> 1;
if(nums[mid] < nums[0]) {
r = mid;
}else {
l = mid + 1;
}
}
return nums[l];
}
}
1.核心思想是二分,二分要保证左右两边有确切不一样的,例如左边都小于等于某个数,右边就是大于;或者相反
2.所以我们开始要while(n >= 0 && nums[n] == nums[0]) n–; 删除右半段等于nums[0]的数据