0154.md

title	description	keywords
154. 寻找旋转排序数组中的最小值 II	LeetCode 154. 寻找旋转排序数组中的最小值 II题解，Find Minimum in Rotated Sorted Array II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 154. 寻找旋转排序数组中的最小值 II 寻找旋转排序数组中的最小值 II Find Minimum in Rotated Sorted Array II 解题思路 数组 二分查找

154. 寻找旋转排序数组中的最小值 II

🔴 Hard  🔖  数组 二分查找  🔗 力扣 LeetCode

题目

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

• [4,5,6,7,0,1,4] if it was rotated 4 times.
• [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates , return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [1,3,5]

Output: 1

Example 2:

Input: nums = [2,2,2,0,1]

Output: 0

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

题目大意

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
• 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

示例 1：

输入： nums = [1,3,5]

输出： 1

示例 2：

输入： nums = [2,2,2,0,1]

输出： 0

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶： 这道题与 寻找旋转排序数组中的最小值 类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

解题思路

这一题是第 153 题的加强版，增加了重复元素的条件，做法没有变，还是用二分搜索，只不过在相等元素上多增加一个判断即可。

创建两个指针 left、right，分别指向数组首尾，然后计算出两个指针所指下标的中间值 mid，将 mid 与两个指针做比较。

• 如果 nums[mid] > nums[right]，则最小值不可能在 mid 左侧，一定在 mid 右侧，则将 left 移动到 mid + 1 位置，继续查找右侧区间。
• 如果 nums[mid] < nums[right]，则最小值一定在 mid 左侧，或者 mid 位置，将 right 移动到 mid 位置上，继续查找左侧区间。
• 如果 nums[mid] == nums[right]，无法判断在 mid 的哪一侧，可以采用 right = right - 1 逐步缩小区域。

复杂度分析

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
	let left = 0,
		right = nums.length - 1;
	while (left < right) {
		let mid = Math.floor((right + left) / 2);
		if (nums[mid] > nums[right]) {
			left = mid + 1;
		} else if (nums[mid] < nums[right]) {
			right = mid;
		} else {
			right--;
		}
	}
	return nums[left];
};

相关题目

题号	标题	题解	标签	难度	力扣
153	寻找旋转排序数组中的最小值	[✓]	数组 二分查找	🟠	🀄️ 🔗