Medium

题目描述

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

请找出其中最小的元素。

你必须设计一个时间复杂度为 O(log n) 的算法解决这个问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5]，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7]，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17]，旋转 4 次得到输入数组。

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数都是唯一的
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路

解题思路

这道题要求在旋转排序数组中找到最小值，时间复杂度必须是 O(log n)，这提示我们使用二分查找。

核心观察：

  • 旋转后的数组可以分为两部分：前半部分的所有元素都大于等于数组的第一个元素，后半部分的所有元素都小于数组的第一个元素
  • 最小值就是旋转点，也就是两部分的分界点

二分查找策略： 我们可以通过比较中间元素与右端点元素的大小关系来判断最小值在哪一侧：

  1. 如果 nums[mid] > nums[right]，说明旋转点在右半部分，最小值在 [mid+1, right] 区间
  2. 如果 nums[mid] < nums[right]，说明右半部分是有序的，最小值在 [left, mid] 区间
  3. 如果 nums[mid] == nums[right]，由于题目保证元素唯一，这种情况不会出现

为什么不用左端点比较？ 因为当 nums[mid] > nums[left] 时，我们无法确定旋转点在哪一侧，比如 [3,4,5,1,2] 和 [1,2,3,4,5] 都满足这个条件。

通过这种方法，每次可以排除一半的搜索空间，最终找到最小值。

代码实现

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]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return nums[left];
    }
};

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = (left + right) // 2
            
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        
        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]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return nums[left];
    }
}

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

复杂度分析

复杂度类型值
时间复杂度O(log n)
空间复杂度O(1)

相关题目