0154. Find Minimum in Rotated Sorted Array II
=============================================
题目信息
--------
:题号: 0154. 寻找旋转排序数组中的最小值 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++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int scanEveryValue(const std::vector& nums) {
return *std::min_element(nums.begin(), nums.end());
}
int binarySearchWithDuplicates(const std::vector& nums) {
int left = 0;
int right = static_cast(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& 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`` 会丢失
答案。
相等只说明这两个位置的值相同,不能判断旋转断点位于中点哪侧,因此不存在安全的半区删除。
为什么 ``--right`` 一定安全
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
可以删除右端这个单独候选。若 ``nums[right]`` 不是最小值,删除显然无害;若它等于全局最小值,因为
``nums[middle] == nums[right]`` 且 ``middle < right``,中点就是同值的另一个最小值,仍留在区间中。算法
可能丢掉一个最小值下标,但不会丢掉全部最小值。
不能对称地在所有相等情况随意同时收缩两端,因为左端未必也有中点这个等值替代;只删除已确认与中点同值
的右端,证明边界最明确。
具体走读带重复的断点
~~~~~~~~~~~~~~~~~~~~
对 ``[2, 2, 2, 0, 1, 2]``:
.. list-table::
:header-rows: 1
* - 区间
- 比较
- 动作
* - ``[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)``;主解的收益是在可辨别时继续利用旋转有序
结构,而相等分支以最小安全删除保持正确性。