LeetCode 154. 寻找旋转排序数组中的最小值 II

约 4 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 困难 已解决 需加强 10-20 腾讯 字节 微软 百度 网易 快手 虾皮
标签
数组 二分查找

题目描述

✅ 154. 寻找旋转排序数组中的最小值 II

image-20260928213919225

image-20260928213919226

题意分析

一个非递减数组经过旋转后，找到其中的最小值。数组非空，允许重复元素，也可能旋转后仍与原数组相同；只需返回最小值，不要求定位它第一次出现的下标。

旋转会把有序数组拆成前后两段，各段内部仍非递减，前段的值不小于后段。没有重复值时通常可以直接判断最小值在哪一侧；有重复值时，相等比较可能隐藏分界，不能每轮都强行排除一半。

解法：二分查找

核心思路

[!blue]

用闭区间 [left, right] 保存候选范围，始终保证其中至少还有一次全局最小值。每轮比较 nums[mid] 与当前右端值，根据大小关系决定可以安全排除的部分。

若 nums[mid] > nums[right]，从中点到右端之间一定跨过了旋转后的下降位置，否则非递减顺序不可能出现前大后小。中点仍在较大的前段，最小值在它右边的后段，因此连同中点一起排除，令 left = mid + 1。

若 nums[mid] < nums[right]，中点到右端不可能跨过从较大前段到较小后段的分界，这一段保持非递减。中点后面的值不会比中点更小，因此不必继续保留它们；但中点自身可能就是最小值，令 right = mid，将它留在候选区间内。

若两者相等，最小值可能在中点的任意一侧，无法判断应该保留哪一半。不过右端仍可以删除：若它不是最小值，删除无影响；若它恰好是最小值，中点还保留着相同值。由于循环中 mid < right，执行 right-- 不会同时删掉这个副本。

三种分支都缩小范围，而且不会丢掉全部最小值候选。最终 left == right，只剩的位置就必然存放最小值。重复值很多时可能连续执行单步缩小，这是重复信息不足带来的最坏情况。

解题步骤

  1. 初始化 left = 0、right = nums.length - 1。
  2. 只要 left < right，计算中点 mid。
  3. 中点值大于右端值时，令 left = mid + 1。
  4. 中点值小于右端值时，令 right = mid，保留可能为答案的中点。
  5. 两者相等时，只令 right--，删除一个有副本的候选。
  6. 区间收敛后返回 nums[left]。

代码实现

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(n)$，元素全部相等时每轮只能删除一个右端点；能持续确定方向时为 $O(\log n)$。
  • 空间复杂度：$O(1)$，只使用固定数量的下标变量。

关键点总结

[!green]

  • 二分依据是候选答案具有可排除的一侧，而不是数组必须整体有序。
  • nums[mid] < nums[right] 时必须保留 mid，所以更新为 right = mid。
  • 相等时没有方向信息；right-- 的正确性来自区间内存在同值副本。

易错点总结

[!yellow]

  • 相等时直接舍弃半个区间：相等比较没有提供最小值的方向信息，可能删掉唯一的更小值。
  • 小于分支写成 right = mid - 1：中点本身可能是答案，应当保留。
  • 相等时随意删除左端：相等的是中点与右端，安全副本只证明右端可删，不能据此删除左端。
  • 只寻找严格下降位置：完全有序、全相等或单元素数组未必存在下降位置，但仍有最小值。
  • 始终声称对数时间：遇到重复值时只减少一个候选，最坏时间会退化为线性。

相似题目

题目 难度 关联与区别
153. 寻找旋转排序数组中的最小值 中等 不含重复值时每次可确定保留的一半，本题遇相等需额外缩小无信息边界。
81. 搜索旋转排序数组 II 中等 同样处理重复旋转数组，原题查找目标，本题定位最小元素。
33. 搜索旋转排序数组 中等 利用旋转数组中仍有序的一半排除搜索区间；本题重复值相等时逐步缩小不确定区间，该题元素互异时定位目标下标。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/03541721
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！