题解 | #旋转数组的最小数字#

描述

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

方法1 暴力求解法

最简单的想法就是撇开旋转数组不谈，直接遍历数组求最小值
时间复杂度 O(n)
空间复杂度 O(1)

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int temp = array[0];
        for(int i=0; i<array.length; i++){
            if(array[i] == 0){
                return 0;
            }
            else if(array[i] < temp){
                temp = array[i];
            }
        }
        return temp;
    }
}

方法2 前后比较法

由于旋转前的数组是非递减数组，所以旋转后只有一个位置有可能出现递减的情况，找到这个位置即可找到最小元素，若没有递减情况，则取第一个元素。
时间复杂度 O(n)
空间复杂度 O(1)

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

方法3 二分法

有没有什么降低时间复杂度的方法呢？我们考虑二分法的时间复杂度为O(logn)，所以我们考虑用二分法解决该问题。当中位元素值小于末位时，最小值一定在前半段；当中位元素大于末位时，最小值一定在后半段。这样就可以利用循环解决大部分情况。但当在处理二分法时，我发现了一个严重的问题， 即当数组某一次循环中头、中、尾三个位置的数值相同时，问题复杂度会回归到O(n)。 理由是在这种情况下无法判断最小值会隐藏在前半段还是后半段中，导致循环进行不下去，下面代码中****部分即为无法解决的情况。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int first =0;
        int last = array.length-1;
        int mid = (first+last)/2;
        while(first<last){
            if(array[mid] < array[last]){
                last = mid;
            }
            if(array[mid] > array[last]){
                first = mid+1;
            }
            if(array[mid] == array[last]){
                if(array[first] != array[mid]){
                    last = mid;
                }
                else{
                    ***************************
                }
            }
             mid = (first+last)/2
        }
        return array[mid];
    }
}

时间复杂度：O(logn) (部分情况除外)
空间复杂度：O(1)