0154. 寻找旋转排序数组中的最小值 II Find Minimum in Rotated Sorted Array II

问题描述

这个问题是 0153 的扩展. 这个表面上看起来可以直用用二分查找法, 但因为可以有相同值的元素存在, 它把问题复杂化了.

暴力法 Brute force

遍历数组, 计算最小值:

#![allow(unused)]
fn main() {
// Brute force
pub fn find_min1(nums: Vec<i32>) -> i32 {
    nums.iter().min().copied().unwrap_or_default()
}
}

时间复杂度是 O(n).

二分查找法

这个要对二分查找法的命中条件做一些改进. 因为有重复元素的存在, 我们在某些条件下无法确定元素的顺序, 但可以只对有明确顺序的情况使用二分查找:

• 如果 nums[middle] < nums[right] 则最小值不在右侧部分
• 如果 nums[middle] > nums[right] 则最小值在右侧部分
• 其它情况, 一次将 left 右移一步, 将 right 左移一步, 渐渐靠近

#![allow(unused)]
fn main() {
// Binary Search
#[allow(clippy::comparison_chain)]
pub fn find_min2(nums: Vec<i32>) -> i32 {
    assert!(!nums.is_empty());

    let mut left = 0;
    let mut right = nums.len() - 1;
    while left + 1 < right {
        let middle = left + (right - left) / 2;
        //println!("left: {left}, middle: {middle} right: {right}, nums: {nums:?}");
        if nums[middle] < nums[right] {
            // (1, 2, 3)
            // 最小值位于左侧
            right = middle;
        } else if nums[middle] > nums[right] {
            // (2, 3, 1)
            // 最小值位于右侧
            left = middle + 1;
        } else {
            // 不容易确定, 一次移动一个位置, 考虑重复的元素.
            if right > left && nums[right - 1] <= nums[right] {
                right -= 1;
            }
            if left < right && nums[left + 1] <= nums[left] {
                left += 1;
            }
        }
    }

    nums[left].min(nums[right])
}
}

该算法的时间复杂度是 O(log(n)).