0154. Find Minimum in Rotated Sorted Array II

题目信息

题号:
  1. 寻找旋转排序数组中的最小值 II

难度:

Hard

主题:

数组、二分查找、重复值消歧、最坏退化

原题:

LeetCode 0154

重点:

保留无重复版本的大小分支,并在中点等于右端时只删除一个有等值替代的端点

题目重述

一个按非递减顺序排列、允许重复值的非空数组经过若干次旋转。给定旋转后数组 nums,返回其中最小值。 应尽量利用有序结构进行二分;重复值可能使最坏时间退化为线性。

自建示例

  • [6, 6, 8, 1, 3, 6]:最小值为 1;

  • [2, 2, 2, 0, 1, 2]:第一次比较可能遇到中点与右端同为 2,缩掉一个右端后才能暴露断点;

  • [4, 4, 4, 4]:所有位置都是最小值候选,返回 4,但每轮只能排除一个重复端点;

  • [1]:单点区间直接返回 1。

C++ 实现

#include <algorithm>
#include <vector>

class Solution {
private:
    int scanEveryValue(const std::vector<int>& nums) {
        return *std::min_element(nums.begin(), nums.end());
    }

    int binarySearchWithDuplicates(const std::vector<int>& nums) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        while (left < right) {
            const int middle = left + (right - left) / 2;
            if (nums[middle] > nums[right]) {
                left = middle + 1;
            } else if (nums[middle] < nums[right]) {
                right = middle;
            } else {
                --right;
            }
        }
        return nums[left];
    }

public:
    int findMin(std::vector<int>& nums) {
        return binarySearchWithDuplicates(nums);
    }
};

题解

重复值改变了哪条信息

数组仍可看成旋转后相接的非递减段,线性扫描仍是 O(n) 的正确基线。上一题能严格二分,依赖 middle < right 时两个不同下标的值必不相等;现在 nums[middle] == nums[right] 可能覆盖断点两侧, 相等不再告诉我们最小值位于哪一半。

闭区间不变量仍然是:[left, right] 内至少保留一个全局最小值下标。算法的每个分支只需保证这个不变量, 最终单点的值就是答案;有多个相等最小值时,不要求保留最初选定的那一个具体下标。

大小明确时为何仍能删除半区

若 nums[middle] > nums[right],中点处于断点前的高值段,右端处于低值段;最小值严格在中点右侧,中点 也不可能是答案,更新 left = middle + 1。

若 nums[middle] < nums[right],从中点到右端没有跨断点,该区间非递减;右侧不可能有比中点更小的值, 但中点可能就是最小值,所以更新 right = middle。重复值没有破坏这两个严格大小关系提供的信息。

相等时为什么不能任选半边

nums[middle] == nums[right] 时,以下两个数组会给出相反要求:

  • [1, 0, 1, 1, 1]:中点和右端同为 1,最小值在中点左侧;若令 left = middle + 1 会丢失 答案;

  • [1, 1, 1, 0, 1]:中点和右端同为 1,最小值在中点右侧;若令 right = middle 会丢失 答案。

相等只说明这两个位置的值相同,不能判断旋转断点位于中点哪侧,因此不存在安全的半区删除。

具体走读带重复的断点

对 [2, 2, 2, 0, 1, 2]:

区间

比较

动作

[0,5],middle=2

nums[2] == nums[5] == 2

无法辨别半区,只改为 [0,4]

[0,4],middle=2

2 > 1

最小值在右侧,改为 [3,4]

[3,4],middle=3

0 < 1

保留中点,改为 [3,3],返回 0

右端缩减并不是盲目线性扫描;它只在重复值使方向信息完全消失时使用,一旦出现严格大小关系,算法立即恢复 半区删除。

为什么最坏无法保证对数时间

在 [4,4,4,...,4] 中,每次 middle 与 right 都相等,没有任何比较能证明某一半不含最小值; 算法只能逐个执行 --right,共 O(n) 轮。这不是实现松懈,而是重复值让不同旋转位置产生完全相同的 观测结果,比较无法提供二分所需信息。

主解选择与复杂度

公开入口采用重复值感知的二分。存在足够多严格比较时通常按半区收缩,接近 O(log n);全相等等极端 输入最坏 O(n),额外空间 O(1)。线性扫描始终 O(n);主解的收益是在可辨别时继续利用旋转有序 结构,而相等分支以最小安全删除保持正确性。