LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.16
• 题目：154. 寻找旋转排序数组中的最小值 II
• 难度：困难
• 标签：数组、二分查找

1. 题目理解

问题描述：
给定一个可能存在重复元素的升序数组，经过1~n次旋转后，找出并返回数组中的最小元素。要求操作步骤尽可能少。

示例：

输入：nums = [2,2,2,0,1] 输出：0 解释：数组中存在重复的2，最小值为0。

输入：nums = [1,3,5] 输出：1 解释：数组未旋转，最小值为1。

2. 解题思路

核心观察

• 与无重复元素的版本（153题）相比，本题存在重复元素，当 arr[mid] == arr[right] 时，无法判断最小值所在区间；
• 解决方法：当 arr[mid] == arr[right] 时，直接将 right--，缩小搜索范围，直到不相等为止；
• 整体逻辑仍基于二分查找，只是在相等时增加了线性步的收缩操作。

算法步骤

1. 初始化左右指针 left = 0，right = nums.length - 1；
2. 循环直到 left == right：
   • 计算 mid = left + (right - left) / 2；
   • 若 arr[mid] > arr[right]：最小值在 mid 右侧，left = mid + 1；
   • 若 arr[mid] < arr[right]：最小值在 mid 左侧，right = mid；
   • 若 arr[mid] == arr[right]：无法判断，right-- 缩小范围；
3. 返回 nums[left]，即为最小值。

3. 代码实现

class Solution {
    int binary(int[] arr, int left, int right) {
        while (left != right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > arr[right]) {
                left = mid + 1;
            } else if (arr[mid] < arr[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return arr[left];
    }

    public int findMin(int[] nums) {
        return binary(nums, 0, nums.length-1);
    }
}

4. 代码优化说明

减少分支判断，将逻辑合并到主函数中，去掉单独的 binary 方法：

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 {
                right--;
            }
        }
        return nums[left];
    }
}

5. 复杂度分析

• 时间复杂度：平均 $O(\log n)$，最坏 $O(n)$

  • 无重复元素时为标准二分查找 $O(\log n)$；
  • 极端情况下（全为重复元素）会退化为线性遍历 $O(n)$。

• 空间复杂度：$O(1)$

  • 仅使用常数级额外变量，无额外空间开销。

6. 总结

• 核心思路：带重复元素的二分查找，利用 right-- 处理 arr[mid] == arr[right] 的情况；
• 关键区别：与无重复元素版本相比，增加了相等时的线性收缩步骤；
• 优化后代码逻辑更紧凑，去掉了不必要的方法调用，可读性和效率更高。