友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
154. 寻找旋转排序数组中的最小值 II
已知一个长度为 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 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
思路分析
这个算法的主结构跟二分查找是一样的：
-
维护两个指针
low、high，使其代表查找范围的左边界和右边界。 -
移动指针来缩小查找范围，通常将指针移动到
low、high的中间(pivot = (low + high)/2)。这样查找范围就可以缩小一半，这也是二分查找名字的由来。 -
在找到目标元素或者两个指针重合时(low == high)，算法终止。
在传统的二分查找中，会将中轴元素(nums[pivot])与目标元素相比较。但在这个问题里面，需要将中轴元素与右边界元素(nums[high])相比较。
二分查找算法的难点在于如何更新左右边界指针。
-
nums[pivot] < nums[high]
中轴元素跟右边界元素在同一半边。这时候最小元素在中轴元素左边，将右边界指针移动到中轴元素位置（
high = pivot）。 -
nums[pivot] > nums[high]
中轴元素跟右边界届元素在不同半边。这时候最小元素在中轴元素右边，将下届指针移动到中轴元素位置右边（
low = pivot + 1）。 -
nums[pivot] == nums[high]
在这种情况下，不能确定最小元素在中轴元素的左边还是右边。
为了缩小查找范围，安全的方法是将右边界指针减一（
high = high - 1）。上述策略可以有效地避免死循环，同时可以保证永远不会跳过最小元素。
综上所述，这个算法跟二分查找有两处不同：
-
这里我们将中轴元素与右边界元素相比较，传统的二分查找将中轴元素与目标元素相对比。
-
当比较结果相同时，这里我们将左移右边界指针，而在传统的二分查找中直接返回结果。
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array II.
* Memory Usage: 39.5 MB, less than 31.25% of Java online submissions for Find Minimum in Rotated Sorted Array II.
*
* Copy from: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui-1-8/[寻找旋转排序数组中的最小值 II - 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-04-25 23:32
*/
public int findMin(int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (nums[pivot] < nums[high]) {
high = pivot;
} else if (nums[pivot] > nums[high]) {
low = pivot + 1;
} else {
high--;
}
}
return nums[low];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-19 20:35:15
*/
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right -= 1;
}
}
return nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-28 23:17:06
*/
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right--;
}
}
return nums[left];
}