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

标签: 数组 二分查找

难度: Hard

已知一个长度为 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 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

Submission

运行时间: 19 ms

内存: 16.5 MB

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        l = -1
        r = n - 1
        ans = inf
        while l + 1 < r:
            m = (r + l) // 2
            if nums[m] > nums[r]:
                l = m 
            elif nums[m] < nums[r]:
                r = m 
            else:
                r -= 1
        return nums[r]

Explain

这个题解使用了二分查找的思路。首先定义左右指针 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)

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        l = -1
        r = n - 1
        ans = inf
        while l + 1 < r:
            m = (r + l) // 2
            if nums[m] > nums[r]:
                # 最小值在右半部分
                l = m 
            elif nums[m] < nums[r]:
                # 最小值在左半部分（包括 m）
                r = m 
            else:
                # 无法判断最小值在哪个部分，缩小右边界
                r -= 1
        # r 指向最小值
        return nums[r]

Explore

在旋转排序数组中，数组可能由两个升序的部分组成。比较中点元素 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] 时，由于数组中存在重复元素，我们不能确定最小值是在左侧还是右侧。但由于 nums[m] 和 nums[r] 相等，我们可以安全地移动 r 指针（r -= 1）来缩小搜索范围，而不会错过最小值。这是因为即使 nums[r] 是最小值，它在 m 位置上也有相同的值，因此不会错过最小值。

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

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