题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。

例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转,该数组的最小值为1。

NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

答案

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0) return 0;
        int start = 0;
        int end = array.length-1;
        while(start<end){
            int mid = (start+end)/2;//数组内部进行判断中位数,最好将首位与末位的下标相加除2,这样免除奇偶的判断
            if(array[mid]<array[end]){
                end = mid;
            }else if(array[mid]>array[end]){
                start = mid+1;
            }
            else{
                end--;
            }
        }
        return array[end];
    }
}

解析

这道题有两种解法,第一种是暴力解,就是遍历整个数组。
当然这种解法肯定是不行的,这道题想考察我们的是二分法思想。

首先了解一下旋转数组,这种数组不是完全排序好的,它是将一个排序好的数组中的末位几个数放到首位,比如12345,变成45123,整体还是排序的。

在这个基础上我们要进行筛选最小数。

核心思想仍然是进行中位数比较,但是我们要考虑不同的情况:

  1. 如果中位数大于右端点
  2. 如果中位数小于右端点
  3. 如果中位数等于右端点

一些基础背景:如果是旋转数组,那么整个数组一定被分为两个升序序列

首先情况1,如果中位数大于右端点,这说明这个中位数一定属于第一序列,同时由于旋转数组的特性,第一序列的首位一定小于等于第二序列的末尾,因此我们可以判断,最小值一定在中位数与末位的中间

然后是情况2,如果中位数小于于右端点,我们可以判断这个中位数属于第二序列,因为第一序列的一定可以续接在第二序列的末位,所以第一序列的整体值都是大于等于第二序列的,那么这种情况下,最小值就有可能是中位值本身,以及中位值到首位中间。

最后是情况3,如果中位值与末位值相等,这说明末位一定不是最小值(或者是最小值之一),这样我们可以直接将末位指针前移


醉后不知天在水,满船清梦压星河