寻找旋转排序数组中的最小值 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 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

代码结果

运行时间: 19 ms, 内存: 16.5 MB

/*
 * Problem: Given a rotated sorted array that may contain duplicates, find the minimum element.
 * Approach: Using Java Stream API to find the minimum element in the array. This approach is less efficient than binary search,
 *           but demonstrates how to use Streams for such problems.
 */
import java.util.Arrays;
 
public class Solution {
    public int findMin(int[] nums) {
        return Arrays.stream(nums).min().getAsInt();
    }
}

解释

方法:

这个题解使用了二分查找的思路。首先定义左右指针 l 和 r，分别指向数组的两端。然后进入循环，每次计算中点 m，比较中点元素 nums[m] 和右端点元素 nums[r] 的大小关系。如果 nums[m] > nums[r]，说明最小值在右半部分，更新 l = m；如果 nums[m] < nums[r]，说明最小值在左半部分（包括 m），更新 r = m；如果相等，无法判断最小值在哪个部分，但可以确定 nums[r] 不是最小值（因为有重复元素），所以可以缩小右边界，更新 r -= 1。最后循环结束时，r 指向的就是最小值的位置。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在二分查找中，为什么选择比较中点元素 nums[m] 和右端点元素 nums[r] 而不是左端点元素 nums[l]？

▷

在旋转排序数组中，数组可能由两个升序的部分组成。比较中点元素 nums[m] 和右端点元素 nums[r] 可以帮助我们判断最小值是否在右半部分。如果 nums[m] > nums[r]，最小值必然在右半部分。而比较 nums[m] 和 nums[l] 时，由于旋转的存在，即使 nums[m] > nums[l]，最小值可能仍在 m 的右侧或左侧，这使得判断更加复杂。因此，比较 nums[m] 和 nums[r] 提供了更清晰的决策基础。

🦆

当 nums[m] == nums[r] 时，我们只是简单地执行 r -= 1，这种处理方式是否可能跳过数组中真正的最小值？

▷

当 nums[m] == nums[r] 时，由于数组中存在重复元素，我们不能确定最小值是在左侧还是右侧。但由于 nums[m] 和 nums[r] 相等，我们可以安全地移动 r 指针（r -= 1）来缩小搜索范围，而不会错过最小值。这是因为即使 nums[r] 是最小值，它在 m 位置上也有相同的值，因此不会错过最小值。

🦆

在二分查找的过程中，l 初始化为 -1 而不是 0，这种初始化方式有什么特殊的考虑或优势吗？

▷

在这段代码中，l 初始化为 -1 是为了与 r 的初始值形成对称，并确保第一次计算中点 m 时能够包含数组的第一个元素。这种初始化方式特别适用于算法的实现方式，其中使用的是 while (l + 1 < r) 循环条件，确保了 l 和 r 最终会收敛在最小值的位置。

🦆

代码中使用了 ans = inf，但似乎并没有在后续代码中使用这个变量。这是代码中的一个错误还是有其他意图？

▷

代码中的 ans = inf 确实没有在后续逻辑中被使用，这看起来是代码遗留的无用部分，或者是原始设计中计划用于某种比较或记录最小值的变量，但在最终实现中被省略了。通常，这应该被视为代码清理的一部分，应该删除以避免混淆。

相关问题