0154. Find Minimum in Rotated Sorted Array II¶
题目信息¶
- 题号:
寻找旋转排序数组中的最小值 II
- 难度:
Hard
- 主题:
数组、二分查找、重复值消歧、最坏退化
- 原题:
- 重点:
保留无重复版本的大小分支,并在中点等于右端时只删除一个有等值替代的端点
题目重述¶
一个按非递减顺序排列、允许重复值的非空数组经过若干次旋转。给定旋转后数组 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会丢失 答案。
相等只说明这两个位置的值相同,不能判断旋转断点位于中点哪侧,因此不存在安全的半区删除。
为什么 --right 一定安全¶
可以删除右端这个单独候选。若 nums[right] 不是最小值,删除显然无害;若它等于全局最小值,因为
nums[middle] == nums[right] 且 middle < right,中点就是同值的另一个最小值,仍留在区间中。算法
可能丢掉一个最小值下标,但不会丢掉全部最小值。
不能对称地在所有相等情况随意同时收缩两端,因为左端未必也有中点这个等值替代;只删除已确认与中点同值 的右端,证明边界最明确。
具体走读带重复的断点¶
对 [2, 2, 2, 0, 1, 2]:
区间 |
比较 |
动作 |
|---|---|---|
|
|
无法辨别半区,只改为 |
|
|
最小值在右侧,改为 |
|
|
保留中点,改为 |
右端缩减并不是盲目线性扫描;它只在重复值使方向信息完全消失时使用,一旦出现严格大小关系,算法立即恢复 半区删除。
为什么最坏无法保证对数时间¶
在 [4,4,4,...,4] 中,每次 middle 与 right 都相等,没有任何比较能证明某一半不含最小值;
算法只能逐个执行 --right,共 O(n) 轮。这不是实现松懈,而是重复值让不同旋转位置产生完全相同的
观测结果,比较无法提供二分所需信息。
主解选择与复杂度¶
公开入口采用重复值感知的二分。存在足够多严格比较时通常按半区收缩,接近 O(log n);全相等等极端
输入最坏 O(n),额外空间 O(1)。线性扫描始终 O(n);主解的收益是在可辨别时继续利用旋转有序
结构,而相等分支以最小安全删除保持正确性。