Java教程

刷题-旋转数组的最小数字

本文主要是介绍刷题-旋转数组的最小数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、题目要求

 

 

二、重点难点分析

  1.首先它是一个升序排列的数组,并旋转了,以至于最小值右边都是小于numbers[right],最小值的左边都是大于numbers[right],所以当中间数小于numbers[right]时,说明此时的right并不是最小值,right要向左边靠,此时 右边界变为 right=mid;当中间数大于numbers[right]时,因为中间数的左边数大于右边的数,所以左边界要向右边靠拢,此时 left(左)=mid +1;

  2.为什么这里可以用到二分?二分的条件是排序的数组,因为旋转之后的数组实际上可以划分为两个排序的子数组,而且前面子数组的元素都是大于或等于后面子数组的元素;而且我们可以注意到最小值其实是这两个子数组的分界线;分别设置两个指针,一个指向最左边(递增子数组)另一个指向最右边(最后一个)

  3.如果该中间元素位于前面的递增子数组,那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素,这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。如果中间元素位于后面的递增子数组,那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面

  4.我的理解:第一个指针总是指向前面递增数组的元素,而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素,而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素,而第二个指针指向的刚好是最小的元素。这就是循环结束的条件

三、代码展示

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
    let left = 0;
    let right = numbers.length - 1;
    while( left <= right){
        let mid = Math.floor((left+right)/2);
        if( numbers[mid] < numbers[right]){
            right = mid;
        }else if( numbers[mid] > numbers[right])
        {
            left = mid + 1;
        }else{
            right -=1;
        }
    }
    return numbers[left];
};

 

这篇关于刷题-旋转数组的最小数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!