题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路和算法复杂度请看方法注释。

package cn.mayday.arroroffer.title6;

/**
 * @description: 旋转数组的最小数字
 * @author: mayday
 * @date: 2019/3/24 10:03
 * @version: 1.0
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(1 == new Solution().minNumberInRotateArray(new int[]{3, 4, 5, 1, 2})); // true

    }

    /**
     * 方法1：直接遍历
     * 找到第一个比前面一个小的元素就能证明这个元素时最小的,时间复杂度 o(n)
     *
     * @param array
     * @return
     */
    public int minNumberInRotateArray1(int[] array) {
        if (null == array || array.length == 0) {
            return 0;
        }
        int temp = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < temp) {
                // 找到第一个比前面一个小的元素，立刻返回结果
                return array[i];
            } else {
                temp = array[i];
            }
        }
        return temp;
    }

    /**
     * 方法2：二分查找
     * <p>
     * 有序数组中查找最小元素，二分查找法。时间复杂度（O（lgn））
     *
     * @param array
     * @return
     */
    public int minNumberInRotateArray(int[] array) {
        if (null == array || array.length == 0) {
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        if (array[left] < array[right]){
            // 正常顺序直接查找
            return array[left];
        }
        while (left < right) {
            // 二分查找
            int middle = left + (right - left) / 2;
            // 如果只剩1-2个元素
            if (middle == left || middle == right) {
                break;
            }
            // 如果middle元素比最左边的小，可以缩小范围，middle右边的数据都可以丢掉
            // 如果middle元素比最右边的小，可以缩小范围，middle右边的数据都可以丢掉
            // 如果middle元素比最右边的大，可以缩小范围，middle左边以及middle的数据都可以丢掉
            if (array[middle] < array[left]) {
                right = middle;
            } else if (array[middle] < array[right]) {
                right = middle;
            } else if (array[middle] > array[right]) {
                left = middle + 1;
            }
        }
        return array[left] > array[right] ? array[right] : array[left];
    }
}