旋转数组最小值II

旋转数组最小值II

题目

一个有序的数组，在从某一个位置开始，旋转到数组的另一端

举例：

0 1 2 3 4 5 6 -> 4 5 6 0 1 2 3

在这个变换之后的数组中，找到最小值。

注意：

• 有可能不旋转的哦。
• 数组元素有重复

题目来自Leetcode: Find Minimum in Rotated Sorted Array II

分析

之前分析过没有重复的情况，最主要的有两点：

1. 考虑完全思路
2. 找好切入点

其实这两点是相关的，一个好的切入点，有利于覆盖完全的思路。这里的切入点可能有，用left，right，mid表示数组的左右中索引：

1. left和mid的数组值关系
2. left和right的数组值关系

right和mid是一样的，那个入手好呢？见下图

left和right的关系少，而且简单。我们不妨从这个开始判断。

其实Leetcode上有问到，有什么变化？其实变化就在于num[left]==num[mid]==num[right]的时候，需要两边都要考虑，不能只考虑一边。

对照着上面的图，大家仔细体会。和图一样粗糙的代码如下：

public class Solution {
    public int min(int a, int b) {
        if (a < b) return a;
        return b;
    }
    
    public int findMin(int[] num, int left, int right) {
        while(left < right) {
            if (num[left] < num[right]) {
                return num[left];
            }
            int mid = (left + right) / 2;
            if (num[left] < num[mid]) {
                left = mid + 1;
            } else if (num[left] > num[mid]) {
                right = mid;
            } else {
                return min(findMin(num, left, mid), findMin(num, mid + 1, right));
            }
        }
        return num[left];
    }
    
    public int findMin(int[] num) {
        return findMin(num, 0, num.length - 1);
    }
}