LeetCode 剑指 Offer 11. 旋转数组的最小数字

约 5 分钟
文章信息 14 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节跳动 微软 美团 阿里巴巴 腾讯 猿辅导 京东 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 二分查找 旋转数组问题
目录

题目描述

✅ 剑指 Offer 11. 旋转数组的最小数字

image-20241107204546899

题意分析

输入是一个「本来非递减排好序、然后被整体旋转过一次」的数组，要求返回其中的最小值。旋转的含义是把前面若干个元素整段搬到末尾，所以数组被切成了两段，每一段内部仍然非递减，且前段的每个元素都不小于后段的每个元素。要找的最小值，就是后段的第一个元素，也就是整个数组里唯一一处「后一个比前一个小」的断点右侧。

有两处约束值得格外注意。第一是「非递减」而不是「严格递增」，也就是说数组里允许出现重复元素，这会直接影响能不能判断出断点在哪一侧。第二是旋转的位数可以是 $0$，即数组可能根本没被旋转，此时它整体有序，最小值就是第一个元素，代码必须能自然覆盖这种退化情况，而不是当成异常。

边界上还要想清楚三种输入：长度为 $1$ 的数组直接返回唯一元素；所有元素完全相同的数组，任何位置都可以看作断点，答案就是那个值；以及后段长度为 $1$ 的数组（比如最小值恰好落在末尾），此时右端点本身就是答案，收缩边界时不能把它误丢掉。

解法：重复元素旋转数组二分

核心思路

旋转数组由两段非递减序列组成，最小值是第二段的起点。用中点与右端点比较，可以判断最小值所在区间：

  • numbers[mid] > numbers[right]：mid 位于较大的前半段，最小值只可能在其右侧，令 left = mid + 1。
  • numbers[mid] < numbers[right]：mid 到 right 已有序，最小值在 mid 或其左侧，令 right = mid。
  • 两者相等：无法判断方向，但删除 right 不会丢失最小值，因为 mid 是它的等值替代，令 right--。

不变量：闭区间 [left, right] 中始终至少保留一个全局最小值。循环结束时区间只剩一个位置，该位置就是答案。重复元素会让第三个分支一次只能排除一个元素，这是最坏退化为线性的原因。

解题步骤

  1. 初始化 left = 0、right = n - 1。
  2. 当 left < right 时计算中点 mid。
  3. 按 numbers[mid] 与 numbers[right] 的大小关系更新边界。
  4. 当 left == right 时返回 numbers[left]。

例如 [2,2,2,0,2]：第一次比较相等，right 从 $4$ 缩到 $3$；之后中点值大于右端值，两次令 left = mid + 1，最终定位到下标 $3$ 的最小值 $0$。

代码实现

class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else if (numbers[mid] < numbers[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return numbers[left];
    }
}

func minArray(numbers []int) int {
    left := 0
    right := len(numbers) - 1
    for left < right {
        mid := left + (right-left)/2
        if numbers[mid] > numbers[right] {
            left = mid + 1
        } else if numbers[mid] < numbers[right] {
            right = mid
        } else {
            right--
        }
    }
    return numbers[left]
}

复杂度分析

  • 时间复杂度：最坏 $O(n)$，全等数组每轮只能执行 right--；不存在重复元素造成的歧义时为 $O(\log n)$。
  • 空间复杂度：$O(1)$，只使用常数个下标变量。

关键点总结

  • 与右端点比较，能判断中点位于最小值之前还是之后；与左端点比较无法自然覆盖未旋转数组。
  • 小于分支必须保留 mid，所以是 right = mid；大于分支确定 mid 不是答案，才写 left = mid + 1。
  • 相等时方向信息消失。[1,0,1,1,1] 与 [1,1,1,0,1] 说明不能武断地舍弃左半或右半。
  • 有重复元素时最坏 $O(n)$ 是算法性质，不应错误宣称始终为 $O(\log n)$。

易错点总结

  • 小于分支写成 right = mid - 1：mid 可能正是最小值，会被错误排除。
  • 大于分支写成 left = mid：在 [2,1] 上区间不缩小，导致死循环。
  • 相等时令 left = mid + 1：[1,0,1,1,1] 会丢掉真正的最小值。
  • 循环条件写成 left <= right：最后会越过唯一候选；闭区间模板应使用 left < right。
  • 中点写成 (left + right) / 2：极大下标相加可能溢出，使用 left + (right - left) / 2。

相似题目

题目 难度 考察点
33. 搜索旋转排序数组 中等 元素互异，判断哪半边有序后再决定目标在哪侧
81. 搜索旋转排序数组 II 中等 在 33 题基础上引入重复元素，需处理三端相等
153. 寻找旋转排序数组中的最小值 中等 无重复版本，可稳定保持 $O(\log n)$
154. 寻找旋转排序数组中的最小值 II 困难 与本题同解，重点在论证最坏退化为 $O(n)$
面试题 10.03. 搜索旋转数组 中等 有重复元素且要求返回下标最小的匹配位置