154. 寻找旋转排序数组中的最小值 II
题目描述
有一个长度为 n 的升序数组，其中可能有相同的数。把它旋转 1 到 n 次，得到输入数组 nums。
旋转一次是指把末尾元素挪到开头：[a[0], a[1], ..., a[n-1]] 变为 [a[n-1], a[0], ..., a[n-2]]。例如 [0,1,4,4,5,6,7] 旋转 4 次得到 [4,5,6,7,0,1,4]。
返回 nums 中的最小元素。请让算法的操作步数尽量少。
示例 1
输入：nums = [1,3,5] 输出：1
解释：数组未被打乱顺序，最小值是 1。
示例 2
输入：nums = [2,2,2,0,1] 输出：0
解释：最小值 0 位于旋转点处。
数据范围
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums由某个升序数组旋转 1 到n次得到。
进阶：本题和第 153 题相似，区别在于元素可以重复。重复元素会不会改变算法的时间复杂度？若会，影响是什么，原因在哪里？
解题思路
拿 nums[mid] 和区间右端 nums[hi] 比较。nums[mid] < nums[hi]：[mid, hi] 有序，最小值在 mid 或其左边，hi = mid。nums[mid] > nums[hi]：断点在 mid 右边，最小值一定在 (mid, hi]，lo = mid + 1。两者相等：无法判断断点在哪侧，但 nums[hi] 有一个等值替身 nums[mid]，去掉 hi 不会丢失最小值，hi -= 1。
为什么正确
最小值始终在 nums[lo..hi] 中。
复杂度分析
平均 O(log n)，全是重复时最坏 O(n)；空间 O(1)。
易错点
不能拿 nums[lo] 比较（未旋转时会走错方向）；相等时不能直接 lo = mid + 1，如 [3,1,3,3,3] 会跳过最小值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[hi]:
hi = mid
elif nums[mid] > nums[hi]:
lo = mid + 1
else:
hi -= 1
return nums[lo]class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] < nums[hi]) {
hi = mid;
} else if (nums[mid] > nums[hi]) {
lo = mid + 1;
} else {
hi--;
}
}
return nums[lo];
}
}class Solution {
public:
int findMin(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] < nums[hi]) {
hi = mid;
} else if (nums[mid] > nums[hi]) {
lo = mid + 1;
} else {
hi--;
}
}
return nums[lo];
}
};func findMin(nums []int) int {
lo, hi := 0, len(nums)-1
for lo < hi {
mid := (lo + hi) / 2
if nums[mid] < nums[hi] {
hi = mid
} else if nums[mid] > nums[hi] {
lo = mid + 1
} else {
hi--
}
}
return nums[lo]
}var findMin = function(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < nums[hi]) {
hi = mid;
} else if (nums[mid] > nums[hi]) {
lo = mid + 1;
} else {
hi--;
}
}
return nums[lo];
};function findMin(nums: number[]): number {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < nums[hi]) {
hi = mid;
} else if (nums[mid] > nums[hi]) {
lo = mid + 1;
} else {
hi--;
}
}
return nums[lo];
}