6.旋转数组的最小数字

佚名 6年前 (2019-04-12) 随笔 1418人围观抢沙发百度已收录

题目描述：

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

思路分析：

由于该题是对有序数组的查找问题，那么我们首先要想到的是运用二分查找思想去解决问题。由题意知旋转数组是将升序数组的尾部一部分放到数组的头部，那么将数组看成两部分，则第一部分是升序，第二部分也是升序，且第一部分数组元素是大于等于第二部分的。那么可以知道第二部分和第一部分的交界处元素就是最小元素。设置两个指针left和right，left指向头部，right指向尾部，始终保持left在第一部分，right指针在第二部分，然后根据中间值和的left指针所指元素大小关系，更新left和right的指针位置，当right和left指针差值为1时，证明找到了两部分的边界，这时right指针所指的数就是最小数，该算法的时间复杂度为O（logn）。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

需要注意的是：

（1）当数组将后面0个元素旋转时，最小元素就是第一个元素。

（2）当left指针和right指针所指的值相同，且等于中间值时，这时候我们无法判断，中间这个值时属于第一部分还是第二部分，也就无法更新left和right缩小查找的范围，这时候只能遍历这个区间找出最小值。

代码：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0||array==null)
        return 0;
        int left=0;
        int right=array.length-1;
        int mid=left; //如果反转了0个元素，那么最小值就是array[0]，所以要将mid初始化为left
        while(array[left]>=array[right]){
            if(right-left==1){   //找到边界的条件
                mid=right;
                break;
            }
            mid=(left+right)/2;
            if(array[left]==array[right]&&array[mid]==array[left]){  //无法判断中间值属于哪部                                                                        分
                return help(array,left,right);
               
            }
            if(array[mid]>=array[left]){
                left=mid;
            }
            else if(array[mid]<=array[left]){
                right=mid;
            }
        }
        return array[mid];
    }
    public int help(int []array,int left,int right){  //遍历方法找区间的最小值
        int res=array[left];
        for(int i=left+1;i<=right;i++){
            if(array[i]<res){
                res=array[i];
            }
          }
        return res;
    }
}