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

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

题目描述

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

image-20241107204546899

题意分析

非递减数组旋转后，至多分成前后两段有序区间，前段的元素不小于后段。需要利用这个结构寻找最小值；数组允许重复，也可能没有旋转，因此不能假设一定能找到严格下降的位置。

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

核心思路

[!blue]

用闭区间 [left, right] 保存候选范围，始终保证其中至少有一个全局最小值。每轮取中点 mid，与当前右端 numbers[right] 比较：

  • numbers[mid] > numbers[right]：从中点到右端跨过了由大值回到小值的断点，右半区一定包含一个最小值。令 left = mid + 1，保留这一侧即可。
  • numbers[mid] < numbers[right]：从中点到右端没有跨过断点，这一段非递减，段内最小值就是 numbers[mid]。右半区即使包含答案，也能用中点代表，所以令 right = mid，保留中点及其左侧。
  • 两者相等：无法判断断点在哪一侧，但可以删掉右端。若右端是最小值，中点就是另一个同值答案；若右端不是最小值，删掉它也没有影响。因此只执行 right--。

循环条件为 left < right，所以 mid 一定在右端之前；三个分支都会严格缩小区间，又不会丢掉所有最小值。最终只剩一个位置，它就是答案。已排序数组、全等数组和单元素数组都适用。

解题步骤

  1. 初始化 left = 0、right = n - 1。
  2. 当 left < right 时计算中点 mid。
  3. 中点值更大时令 left = mid + 1；更小时令 right = mid；相等时令 right--。
  4. 当 left == right 时返回 numbers[left]。

代码实现

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)$，只使用常数个下标变量。

关键点总结

[!green]

  • 二分只需保留至少一个最小值；重复的最小值可以分布在不同位置，不必全部保留。
  • 小于分支必须保留 mid，所以是 right = mid；大于分支确定 mid 不是答案，才写 left = mid + 1。
  • 相等时没有足够信息舍弃整整一半，安全的做法是去掉右端的一个同值候选。
  • 有重复元素时最坏 $O(n)$ 是算法性质，不应错误宣称始终为 $O(\log n)$。

易错点总结

[!yellow]

  • 小于分支写成 right = mid - 1：mid 可能正是最小值，会被错误排除。
  • 大于分支写成 left = mid：只剩两个候选时，mid == left，区间不会缩小。
  • 相等时直接舍弃某一半：中点与右端同值不能说明较小元素在哪一侧，可能把唯一的最小值删掉。

相似题目

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