Hard

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 nums = [0,1,4,4,5,6,7] 可能变为：

  • [4,5,6,7,0,1,4] 如果它被旋转了 4 次。
  • [0,1,4,4,5,6,7] 如果它被旋转了 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 可能包含重复元素。这会影响算法的时间复杂度吗？如何影响，为什么？

解题思路

这是一道在旋转排序数组中寻找最小值的问题，与153题的区别是数组中可能包含重复元素。

核心思路： 使用二分查找来缩小搜索范围，通过比较中点与边界值来判断最小值的位置。

算法分析：

  1. 基本情况： 如果 nums[left] < nums[right]，说明当前区间已经有序，最小值就是 nums[left]
  2. 三种比较情况：
    • 若 nums[mid] < nums[right]，说明右半部分有序，最小值在左半部分（包括mid）
    • 若 nums[mid] > nums[right]，说明左半部分有序，最小值在右半部分
    • 若 nums[mid] == nums[right]，这是重复元素带来的困扰，无法确定最小值位置

关键难点： 当 nums[mid] == nums[right] 时，我们无法确定最小值在哪一侧。此时只能将 right--，逐步缩小范围。这种情况下，最坏时间复杂度会退化到 O(n)。

示例分析： 对于 [2,2,2,0,1]，当所有元素都相等时，必须逐个检查才能找到不同的元素。

这种处理重复元素的策略是最优的，既保证了正确性，又在大多数情况下保持了较好的性能。

代码实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 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];
    }
};

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] < nums[right]:
                right = mid
            elif nums[mid] > nums[right]:
                left = mid + 1
            else:
                right -= 1
        
        return nums[left]

public class Solution {
    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];
    }
}

var findMin = function(nums) {
    let left = 0, right = nums.length - 1;
    
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] < nums[right]) {
            right = mid;
        } else if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right--;
        }
    }
    
    return nums[left];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n) ~ O(n)平均情况下为 O(log n)，最坏情况下当所有元素都相等时退化为 O(n)
空间复杂度O(1)只使用了常数级别的额外空间

相关题目