题目描述：

假设你有一个按非降序排列的数组，并且数组中的元素在某个点上进行了旋转，变成了一个旋转排序数组。你需要找到这个旋转排序数组中的最小值。

注意：

  • 数组可能存在重复元素。
  • 你必须在 O(log n) 时间复杂度内解决这个问题。

示例：

示例 1:

输入:
[1, 3, 5]
输出:
1

示例 2:

输入:
[2, 2, 2, 0, 1]
输出:
0

问题分析：

在这道题中，旋转排序数组意味着数组的某个部分被旋转并移到了数组的前面。由于允许数组中存在重复元素，我们不能单纯地通过比较中间元素与两端元素的大小来决定最小值的位置，这使得这个问题比传统的旋转排序数组中的最小值查找稍微复杂。

我们可以采用二分查找的方法来优化查找过程。

解决思路：

我们可以利用二分查找来解决这个问题，思路如下：

  1. 初始化：定义 left 和 right 指针，分别指向数组的左右两端。
  2. 二分查找：在每次迭代中，计算 mid（中间位置），然后判断 nums[mid] 与 nums[left]、nums[right] 的关系：
    • 如果 nums[mid] > nums[right]，说明最小值在 mid 右边，left = mid + 1。
    • 如果 nums[mid] < nums[right]，说明最小值在 mid 或者 mid 左边，right = mid。
    • 如果 nums[mid] == nums[right]，此时无法确定最小值在哪一边，因此我们可以缩小搜索范围，right = right - 1。
  3. 终止条件：当 left == right 时，nums[left] 即为最小值。

时间复杂度：

  • 由于每次比较时都能排除一部分元素，最坏情况下时间复杂度为 O(n)，这比传统的 O(log n) 时间复杂度稍差。但由于我们采用了二分查找方法，尽管存在重复元素，仍然能在 O(n) 的时间内找到最小值。

代码实现：

def findMin(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        # If the middle element is greater than the rightmost element,
        # the minimum must be to the right of mid.
        if nums[mid] > nums[right]:
            left = mid + 1
        # If the middle element is less than the rightmost element,
        # the minimum must be at mid or to the left of mid.
        elif nums[mid] < nums[right]:
            right = mid
        # If the middle element is equal to the rightmost element,
        # we cannot be sure which side the minimum is on, so we reduce the search space.
        else:
            right -= 1

    return nums[left]

解释：

  1. 初始化：left 和 right 分别指向数组的两端。
  2. 循环：在循环中，我们每次计算 mid，然后根据 nums[mid] 和 nums[right] 的大小关系来缩小搜索范围：
    • 如果 nums[mid] > nums[right]，则说明最小值在 mid 的右边，更新 left = mid + 1。
    • 如果 nums[mid] < nums[right]，则最小值可能在 mid 左边，更新 right = mid。
    • 如果 nums[mid] == nums[right]，我们无法确定最小值在哪一边，只能将 right 移动一位 (right -= 1) 来减少搜索范围。
  3. 终止条件：当 left == right 时，left 指向的元素即为最小值。

测试用例：

  1. 输入： [1, 3, 5]
    输出： 1
    解释： 数组没有旋转，因此最小值是 1。
  2. 输入： [2, 2, 2, 0, 1]
    输出： 0
    解释： 数组旋转后，最小值是 0。
  3. 输入： [4, 5, 6, 7, 0, 1, 2]
    输出： 0
    解释： 数组旋转后，最小值是 0。
  4. 输入： [1, 3, 5, 1, 1, 1]
    输出： 1
    解释： 数组旋转后，最小值是 1，注意存在重复元素。

总结

这道题考察了旋转排序数组中最小值查找的二分查找方法，同时处理了数组中可能存在重复元素的情况。通过合理利用 left 和 right 的比较，可以在 O(n) 时间复杂度内找到旋转数组中的最小值。