剑指offer最优解Java版-旋转数组的最小数字

题目描述

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

第一种方案：遍历

遍历数组，当出现array[i] > array[i + 1]，则array[i+1]就是答案，如果遍历结束都没出现答案，说明第一个数字是最小的

class Solution {
  public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        if (array.length == 1) {
            return array[0];
        }
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                return array[i + 1];
            } 
        }
        return array[0];
    }
}

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

第二种方案：二分查找

class Solution {

    public static int minNumberInRotateArray(int [] array) {
        if(array == null || array.length == 0) return 0;
        int start = 0;
        int end = array.length - 1;
        int mid = (start + end) / 2;
        if(array[end] == array[start] || array[mid] == array[end] || array[mid] == array[start]){
            return findMin(array);
        }
        // 出现下列情况，无法判断最小值位置，所以只能遍历
        if(array[mid] > array[start] && array[mid] < array[end]){
            return array[0];
        }
        while(true){
            mid = (start + end) / 2;
            if(array[mid] > array[start]){
                start = mid;
            }else if(array[mid] < array[end]){
                end = mid;
            }
            // 加入只有4和6，mid和start都对应4，end对应6。所以必须要大于等于
            if((start+1) >= end) break;
        }
        return array[end];
    }

    public static int findMin(int[] array){
        int result = Integer.MAX_VALUE;
        for(int i = 0; i <= array.length - 1; i++){
            result = Math.min(result, array[i]);
        }
        return result;
    }

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

复杂度分析：

• 时间复杂度：最好的情况O(logn)，最坏情况O(n)。
• 空间复杂度：O(1)。

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我