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)``;主解的收益是在可辨别时继续利用旋转有序 结构,而相等分支以最小安全删除保持正确性。