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

标签: array, binary-search

难度: Hard

通过率: 43.88%

原题链接: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/

题目描述

假设一个按升序排列的数组在某个未知点进行旋转。也就是说，该数组的某个前缀被移到了数组的尾部。需要注意的是，数组可能包含重复的元素。给定这样的数组，返回数组中的最小值。

解题思路

本题是 Find Minimum in Rotated Sorted Array 的进阶版本，这个版本允许数组中存在重复的元素。我们使用二分查找的方法来解决该问题。```

1. 初始化两个指针left和right分别指向数组的头和尾。
2. 在每次循环中，根据下标mid = (left + right) // 2获得中间元素。
3. 如果nums[mid]大于nums[right]，说明最小值在右半部分，因此我们需要将left移动到mid + 1。
4. 如果nums[mid]小于nums[right]，说明最小值在左半部分，故我们调整right指针至mid。
5. 当nums[mid]等于nums[right]时，由于无法判断最小值在哪一侧，将right左移一位，来跳过重复的元素。根据这种做法可以保证最小值不会被跳过。

通过以上过程，left最终会指向最小值。```

这一算法有效地结合了二分查找与线性扫描处理重复数据的优势，在保证复杂度的情况下很好地解决了问题。

代码实现

Python

def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            # 最小值在右边
            left = mid + 1
        elif nums[mid] < nums[right]:
            # 最小值在左边或就是mid
            right = mid
        else: # nums[mid] == nums[right]
            # 无法决定，缩小右侧边界
            right -= 1
    # 最小值为left
    return nums[left]

C++

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 if (nums[mid] < nums[right]) {
            // 最小值在左半部分
            right = mid;
        } else {
            // nums[mid] == nums[right]
            // 缩小右侧边界
            right--;
        }
    }
    return nums[left];
}

JavaScript

function findMin(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            // 最小值在右边
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            // 最小值在左边
            right = mid;
        } else { // nums[mid] == nums[right]
            // 无法判断，缩小右侧边界
            right--;
        }
    }
    return nums[left];
}

Java

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 if (nums[mid] < nums[right]) {
                // 最小值在左边
                right = mid;
            } else { // nums[mid] == nums[right]
                // 无法判断，缩小右侧边界
                right--;
            }
        }
        return nums[left];
    }
}

复杂度分析

时间复杂度为 $O(n)$，因为在最坏情况下（数组中所有元素相同），对每个元素进行一次比较。

空间复杂度为 $O(1)$，因为只使用了固定数量的额外空间。