剑指Offer对答如流系列 -旋转数组的最小数字

面试题10：旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

时间复杂度要求小于O(n)

问题分析

可以了解到，数组即使在转换之后在一定形式上也是递增的。

在动手之前，先考虑一下可能的场景：

1. 移动的元素数量大于0，且数组中没有重复的元素

2. 移动的若干元素的 若干 包含0。若干表示一个不定数目。

3. 递增的数组元素中，可能有相同的。

很多时候，我们无法一次性写出满足所有场景的代码，我们可以先从简单的做起，比如说先考虑第一条。

明确存在的场景之后，下面就是考虑问题的解决思路了，这里比较容易想到，对于排序的数组中的查找，二分查找是非常好的手段。

问题解答

下面针对第一个场景，进行解决。

经过旋转的数组中，有两个递增数组，我们其中有着较小元素的数组是我们需要的。
当我们使用二分查找法的时候，如果中间的元素位于前面的递增子数组，那么它应该大于或者等于第一个元素，此时数组中最小的元素位于该中间元素的后面。（3,5,1的关系）

反之，如果中间元素位于后面的递增子数组，那么它应该小于第一个元素，此时数组中最小的元素位于该中间元素的前面。

 public int min(int[] array) {
        if (array == null || array.length <= 0) {
            // 空数组或null时返回0
            return 0;
        }
        if(array.length == 1) {
            // 如果是一个元素直接返回
            return array[0];
        }
     
        int low = 0;
        int high = array.length - 1;
        int mid;
        while (low < high) {
            mid = (low + high) / 2;
            if (array[mid] <= array[high])
                high = mid;
            if (array[mid] > array[high])
                low = mid;
        }
        return array[high]; 
    }

现在考虑第二种场景的解决（其实非常简单）

加一项判断。如果第一个元素小于最后的元素，这说明是升序数组，直接返回第一个元素即可。

 if (array[low] < array[high]) {
            return array[low];
 }

现在考虑第三种场景，相同元素带来的恶果就是 中间数字与首尾数字相等 我们无法判断中间元素位于哪个递增子数组

这种情况下，只能遍历。

整体的代码如下 ；

 public int min(int[] array) {
        if (array == null || array.length <= 0) {
            // 空数组或null时返回0
            return 0;
        }
        if(array.length == 1) {
            // 如果是一个元素直接返回
            return array[0];
        }
        
        int low = 0;
        int high = array.length - 1;
        int mid ;
        // 情况2
        if (array[low] < array[high]) {
            return array[low];
        }

        while (low < high) {
            mid = (low + high) / 2;
            // 情况3
            if (array[mid] == array[high] && array[mid] == array[low]) {
                for (int i = 1; i <= high; i++) {
                    if (array[i] < array[i - 1]) {
                        return array[i];
                    }
                }
                return array[low];
            } else if (array[mid] <= array[high]) {
                high = mid;
            } else {
                low = mid;
            }
        }
        return array[high];
    }