题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
import java.util.*;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int low = 0 ;
int high = array.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (array[mid] > array[high]) {
low = mid + 1;
} else if (array[mid] == array[high]) {
high = high - 1;
} else {
high = mid;
}
}
return array[low];
}
}
这题虽然已经有了二分法的提示还是没想到如何写，但是我用寻找峰值的方法改成寻找谷值的，差点成功了，因为有些情况较难考虑到，而且该方法也比较烂，最终在评论区找到了该代码，该代码来自FINACK
下面是代码思路：
采用二分法查找旋转数组中的最小值时，我们需要考虑数组的特点：旋转数组是由两个有序数组组成的，其中一个数组的所有元素都大于另一个数组的所有元素。我们的目标是找到这两个数组的分界点，即旋转数组中的最小值。二分法的三种情况如下：
- 情况一：
array[mid] > array[high]这种情况说明 mid 位于左边的有序数组中，而最小值位于 mid 的右边。因此，我们将搜索范围缩小到右半部分，即 low = mid + 1。 - 情况二：
array[mid] == array[high]这种情况比较复杂，因为无法确定 mid 是在左边数组还是在右边数组。例如，数组可能是 [1, 0, 1, 1, 1] 或者 [1, 1, 1, 0, 1]。在这种情况下，我们无法确定最小值是在 mid 的左边还是右边，因此只能将 high 减一，即 high = high - 1，这样就去掉了一个可能的重复值。 - 情况三：
array[mid] < array[high]这种情况说明 mid 位于右边的有序数组中，而最小值可能是 mid 本身或者在 mid 的左边。因此，我们将搜索范围缩小到左半部分，即 high = mid。 注意，当 low 和 high 相邻时，即 low == high，mid 将等于 low。在这种情况下，如果 array[mid] > array[high]，则最小值在 mid 的右边，我们设置 low = mid + 1 是正确的。但如果 array[mid] < array[high]，则最小值可能是 mid 本身或者在 mid 的左边，我们设置 high = mid 也是正确的。这是因为当 low 和 high 相邻时，mid 总是指向 low，所以 high = mid 不会错过最小值。 总结一下，二分法查找旋转数组中的最小值的步骤如下：
- 初始化
low为数组的起始位置，high为数组的结束位置。 - 当
low < high时，执行二分查找： 计算中点 mid = low + (high - low) / 2。如果 array[mid] > array[high]，则最小值在 mid 的右边，设置 low = mid + 1。如果 array[mid] == array[high]，则将 high 减一，即 high = high - 1。如果 array[mid] < array[high]，则最小值可能是 mid 本身或者在 mid 的左边，设置 high = mid。 - 当
low == high时，循环结束，low或high就是数组中的最小值。
查看6道真题和解析
人太多了害