《剑指offer第二版》面试题11:旋转数组的最小数字(java

2020-03-08  本文已影响0人  castlet

题目描述

把一个数组最开始的的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1.

解题思路:

  1. 数组可以分为两个递增数组A和B,则第二个递增数组B里的所有数字都小于等于第一个递增数组A里的数字。B的开头即为最小数字。
  2. 采用二分查找的方式。用三个变量分别表示数组的开头,中间和结尾。
  3. 如果中间数字大于等于开头数字,则说明中间数字在递增数组A里,最小数字一定在中间数字之后。
  4. 再对中间数字之后的数字进行二分查找即可。

代码

int min(int[] arr){
    if (arr == null || arr.length == 0) {
        return -1;
    }

    int startIndex = 0;
    int endIndex  = arr.length - 1;
    int middleIndex = startIndex;

    // 如果开头数字小于结尾数字,说明递增数组并没有旋转,第一个数字就是最小数字。
    if (arr[startIndex] < arr[endIndex]) {
        return arr[startIndex];
    }

    while(startIndex < endIndex) {
        if (endIndex - startIndex == 1) {
            return arr[endIndex];
        }
        middleIndex = startIndex + (endIndex - startIndex) / 2;
        if (arr[startIndex] == arr[endIndex]  && arr[startIndex] == arr[middleIndex]) {
            // 三个值相等的话,采用顺序查找的方式
            int min = arr[startIndex];
            for (int i = startIndex; i <= endIndex; i++) {
                if (arr[i] < min) {
                    min = arr[i];
                }
            }
            return min;
        }

        if (arr[middleIndex] >= arr[startIndex]) {
            // middleIndex对应的数字在前面的递增数组里,则最小值在middleIndex之后
            startIndex = middleIndex;
        } else if (arr[middleIndex] < arr[endIndex]) {
            endIndex = middleIndex ;
        }
    }
    return -1;
}
上一篇下一篇

猜你喜欢

热点阅读