描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路

暴力排序 时间复杂度O(nlogn) ,空间复杂度O(1)

1. 顾名思义，排序后输出最小的值即可

   假设[1,2,3,4,5]旋转后为[3,4,5,1,2], 排序后为[1,2,3,4,5],则 array[0]即为最小值

    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0){
            return 0;
        }
        // 排序
        Arrays.sort(array);
        // 输出最小的
        return array[0];
    }

优化方法 时间复杂度O(n),空间复杂度O(1)

由题意给出的数组是一个非递减排序， 把一个数组最开始的若干个元素搬到数组的末尾，旋转后会破坏数组的非递减排序，会使数组的最大值在数组最小值之前，即会出现arr[i] > arr[i+1]，那么arr[i+1]即我们要找的最小值，利用这个特性可以得到以下代码

    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0){
            return 0;
        }
        for (int i = 1 ; i < array.length ; i++){
            // 只要出现array[i-1] > array[i]就可以确认array[i]为要找的数
            if (array[i-1] > array[i]){
                return array[i];
            }
        }
        return array[0];
    }

举例

假设[1,2,3,4,5]旋转后为[3,4,5,1,2], 当满足array[i]>array[i+1]即5>1，所以输出array[i+1]即1