剑指offer题解—查找和排序

【牛客】旋转数组的最小数字

题目描述

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

解题思路

  1. 只说要找最小值,因此可以直接排序。
 public int minNumberInRotateArray(int [] array) {
        Arrays.sort(array);
        return array[0];
    }
  1. 二分

    观察数组可以了解到,对于最小值有这样一个特性:只有最小值的左右两边都比他大(看起来像废话)。通过修改二分查找,就可以求出结果。

    当array[mid] 大于左边界时,说明mid还是在左边的子数组里的,此时就可以更新l的值,l=mid , 因为最小值肯定在第一个子数组结束后的第一个位置,换言之不在第一个子数组里。

    当array[mid]小于右边界时,说明mid在第二个子数组里,此时就可以更新r的值

    通过修改mid的值,不断逼近最小值即可求得结果。

public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length == 0) return 0;
        int l = 0;
        int r = array.length - 1;

        while(l < r - 1){
            int mid = (l +r) >> 1;
            if (array[mid] >= array[l])
                l = mid;
            if (array[mid] <= array[r])
                r = mid;
        }
       return array[r];
    }

参考

  1. https://www.bilibili.com/video/BV1iJ41177Zw
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复