简单粗暴:遍历
就不多介绍了,大家都懂
时间复杂度:O(n)
空间复杂度:O(1)
思路1的代码实现如下
/**
* 暴力破解法
*
* @param num 给定的旋转后数组
* @return 查询结果
*/
public static int findMin(int[] num) {
if (num == null || num.length == 0) {
return -1;
}
int min = num[0];
for (int i = 0; i < num.length; i++) {
if (num[i] < min) {
min = num[i];
}
}
return min;
}
还是那句话
凡是看到有序或者局部有序的数组查找问题
第一个想到的就应该是用二分法试试
下面我们来分析一下
一个增序的数组是这样的
旋转n次之后就是这样的
所以我们的目标就是在这样的数组里边找目标值
可以非常清晰的看到
第二段的所有值都是小于第一段的值
所以最小值就是在二段的第一个元素
还有一种极端的情况就是
经过多次旋转之后
数组又变成了一个单调递增的数组
此时的最小值就是第一个元素
我们用数组[1,2,3,4,5,6,7,8,9]举例说明
3次旋转之后是这个样子
此时我们还不知道这个数组是分了两段
还是单调递增的
使用二分查找的话,首先还是先找到中位数
start=0,nums[start]=4
end=8,nums[end]=3
mid为(0+8)/2=4,nums[mid]=8
此时nums[mid]>nums[start]
说明mid在第一段区间(或者整个数据都是单调递增的)
同时nums[mid]>nums[end]
由此可知:最小值存在于mid~end之间
接下来就是对mid~end之间的内容再次进行二分查找
start=4,nums[start]=8 start=8,nums[end]=3 mid=6,nums[mid]=1
此时nums[mid]<nums[start]
说明mid在第二段区间(或者整个数据都是单调递增的)
end必然也是在第二段区间(或者整个数据都是单调递增的)
所以可以判断出最小值必然存在第二段
也就是最小值存在于mid~end之间
此时问题就简化为了在一个单调递增的区间中查找最小值了
所以总的规律就是:
在二分法的基础上
当中间值mid比起始值start对应的数据大时
判断一下mid和end对应值的大小 nums[end]<=nums[mid],则最小值在mid后边,start=mid nums[end]>nums[mid],则最小值在mid前边,end=mid
思路2的代码实现如下
public static int findMin(int[] num) {
if (num == null || num.length == 0) {
return -1;
}
int start = 0;
int end = num.length - 1;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (num[mid] >= num[start]) {
if (num[end] <= num[mid]) {
start = mid;
} else {
end = mid;
}
} else {
end = mid;
}
}
return Math.min(num[start], num[end]);
}
时间复杂度:O(logn)
空间复杂度:O(1)
文/戴先生@2022年07月09日