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

难度: 🌕

问题描述

---

解法

class Solution {
    public int findMin(int[] nums) {
        // 思路：
        // 二分 - 数组含重复元素
        int len = nums.length;
        return mySol(nums, 0, len - 1);
    }

    private int mySol(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return nums[left];
        }
        if(left == right - 1) {
            return Math.min(nums[left], nums[right]);
        }
        // 节点数 >= 3 中点必不与 left 重合
        int mid = left + ((right - left) >> 1);
        // 特殊情况特判
        if(nums[mid] < nums[mid - 1]) {
            // [mid] 为最小值
            return nums[mid];
        }
        if(nums[mid] > nums[mid + 1]) {
            return nums[mid + 1];
        }
        // mid 左右附近单增，不存在旋转点
        if(nums[mid] < nums[right]) {
            // 右侧非严格单增
            return mySol(nums, left, mid - 1);
        } else if(nums[mid] == nums[right]) {
            return mySol(nums, left, right - 1); // 打破现状
        } else {
            return mySol(nums, mid + 1, right);
        }
    }
}

---

输出