美文网首页程序员
剑指offer----旋转数组中最小的数字

剑指offer----旋转数组中最小的数字

作者: qming_c | 来源:发表于2018-02-02 20:25 被阅读0次

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

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

二分查找

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

使用二分查找的话,思想与正常的二分查找类似,通过low,high,mid三个指针,不断的通过low,和high两个指针向mid上靠拢,并同时更新mid,来不断的缩小查找范围。不同的问题主要就是比较条件的不同。
在这个题目中是根据high和mid指针所对应的数值的比较来判断如何更新high和low两个指针的。

用high,low,mid来分别带别数组中对应的指针。
具体如下

  • 当mid >high 时说明,最小的数在mid后面的部分,所以要将mid及mid前面的数过滤掉,将low指针更新到mid的下一位。
  • mid < high时说明,从mid到high是递增的,即mid后面的数都大于mid所以,更新high=low,即将mid后面的数过滤掉(不包括mid)。
  • mid = high时,后面的数都是与mid相等的,我最开始的时候想将这一中情况与mid < high的情况放到一起,直接将让high = mid。 虽然牛客的测试用例通过了,但是看到评论里有人说
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1],此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ,
high = high - 1

如果发生这种情况,正确的返回结果应该0,但是第二种此时mid是1,high也是以1,将high = mid,直接将0给过滤掉了,最终返回的是1,所以需要加一个判断。

相关文章

网友评论

    本文标题:剑指offer----旋转数组中最小的数字

    本文链接:https://www.haomeiwen.com/subject/kjoezxtx.html