LeetCode 154. 寻找旋转排序数组中的最小值 II
目录
题目描述
题意分析
输入是一个原本按非递减顺序排好的数组，被整体「旋转」了若干次——也就是把开头若干个元素整段搬到了末尾，要求输出其中的最小元素。
旋转的结果是：数组被切成前后两段，每一段内部仍然有序，且前段的每个元素都不小于后段的每个元素，最小值恰好位于两段的接缝处。旋转次数可能为零，此时数组保持原样，最小值就在开头。
与前一版本最大的差别在于「可能包含重复元素」这句话。重复元素让「比较两个位置的值就能判断接缝在哪一侧」这件事失效：当两端的值一样时，接缝既可能在左边也可能在右边，仅凭这一次比较得不出任何结论。
约束还告诉我们数组非空，因此不必考虑无解；元素可以全部相同，此时任意位置都是最小值。边界上要留意只有一个元素、以及整个数组完全没被旋转这两种情况。
解法：二分查找
核心思路
数组虽然被旋转，但仍由两段非递减序列组成。在线性扫描之外，更合适的面试解法是在候选区间
[left, right]中二分，并用nums[right]判断最小值在哪一侧：
nums[mid] > nums[right]：mid位于较大的前半段，最小值一定在mid右侧。nums[mid] < nums[right]：mid已位于包含最小值的后半段，最小值在[left, mid]。nums[mid] == nums[right]：重复值抹平了分段信息，无法判断方向，只能令right--。循环不变量是：闭区间
[left, right]内始终至少保留一个全局最小值。 前两个分支根据严格大小关系排除不可能区域；相等时即使right是最小值，mid处也有相同值，因此删除right仍保留最小值的数值。当
left == right时，候选区间只剩一个位置，它就是答案。重复值会让区间每次只能缩小一格，所以最坏复杂度会退化为线性。
解题步骤
- 初始化
left = 0、right = nums.length - 1。- 当
left < right时，计算mid = left + (right - left) / 2。- 若
nums[mid] > nums[right]，令left = mid + 1。- 若
nums[mid] < nums[right]，令right = mid，因为mid本身可能是最小值。- 若两者相等，令
right--，保守地去掉一个重复值。- 循环结束后返回
nums[left]。例如
[2, 2, 2, 0, 1]：第一次比较得到2 > 1，搜索区间缩到[3, 4]；随后0 < 1，区间缩到[3, 3]，返回0。而[3, 3, 1, 3]首轮会进入相等分支，说明该分支不能直接砍掉一半。
代码实现
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
// 重复值无法判断方向，安全丢弃一个右端点。
right--;
}
}
return nums[left];
}
}
func findMin(nums []int) int {
left := 0
right := len(nums) - 1
for left < right {
mid := left + (right-left)/2
if nums[mid] > nums[right] {
left = mid + 1
} else if nums[mid] < nums[right] {
right = mid
} else {
// 相等时无法排除 mid，只缩小 right。
right--
}
}
return nums[left]
}
复杂度分析
- 时间复杂度：能持续判断方向时为 $O(\log n)$，最坏为 $O(n)$。例如元素全部相等时，每轮只能执行一次
right--。- 空间复杂度：$O(1)$，只使用常数个下标变量。
关键点总结
- 二分依据是候选答案具有可排除的一侧，而不是数组必须整体有序。
nums[mid] < nums[right]时必须保留mid，所以更新为right = mid。- 相等时没有方向信息；
right--的正确性来自区间内存在同值副本。- 面试时应主动说明：允许重复元素后，最坏时间复杂度不再保证为 $O(\log n)$。
易错点总结
- 相等时令
right = mid：对[3, 3, 3, 1, 3]会直接丢掉最小值所在的右半段。- 小于时令
right = mid - 1：对[3, 1, 2]，mid恰好是最小值，会被错误排除。- 相等时随意令
left++：对[1, 3, 3]会丢掉唯一的最小值1。- 声称复杂度始终是 $O(\log n)$：全相等数组会连续执行
right--，实际为 $O(n)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 33. 搜索旋转排序数组 | 中等 | 找指定目标而非最小值，需先判断哪半段有序 |
| 81. 搜索旋转排序数组 II | 中等 | 同样有重复元素，但相等时要同时收缩左右两端 |
| 153. 寻找旋转排序数组中的最小值 | 中等 | 元素互不相同，没有相等分支，稳定 $O(\log n)$ |
| 剑指 Offer 11. 旋转数组的最小数字 | 简单 | 与本题同题换皮，可用来对照两种模板写法 |
| 面试题 10.03. 搜索旋转数组 | 中等 | 有重复且要求返回下标最小的匹配位置，收缩规则更严格 |