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

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

作者: castlet | 来源:发表于2020-03-08 12:51 被阅读0次

    题目描述

    把一个数组最开始的的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组{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;
    }
    

    相关文章

      网友评论

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

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