0154.md

title	description	keywords
154. 寻找旋转排序数组中的最小值 II	LeetCode,154. 寻找旋转排序数组中的最小值 II,寻找旋转排序数组中的最小值 II,Find Minimum in Rotated Sorted Array II,解题思路,数组,二分查找	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?

题目大意

假设按照升序排序的数组在预先未知的某个点上进行了旋转。(例如，数组 [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。请找出其中最小的元素。

注意数组中可能存在重复的元素。

解题思路

这一题是第 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	寻找旋转排序数组中的最小值	[✓]	数组 二分查找	Medium