旋转数组的最小数字

2021年10月28日

题目:

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

示例:

示例一:

输入:[3,4,5,1,2]
输出:1

示例二:

输入:[2,2,2,0,1]
输出:0

思路

首先要理解数组的旋转这个概念,我的理解是:将数组从一个位置分为两个子数组,将这两个子数组之间的先后顺序交换,子数组内部的顺序不变。题目中给出的条件是输入的是递增排序的数组的旋转。从题目中给出的例子也可以看到,较小的子数组被旋转到了后面。所以如果从前往后遍历输入的数组的话,当遍历到一个数字比它前面的一个数字小,根据旋转的定义,旋转之后的两个子数组内部也一定是递增的,所以可以说明和前面那个数字不属于同一个子数组。该数字还是该子数组的第一个数字,也就是该子数组中最小的数字。因为这个子数组位于整个数组的后半部,所以旋转前它就是位于前半部,所以这个数字就是旋转前的递增数组的第一个数字,也就是我们要找的最小的数字。

注意:

当遍历完了整个数组还没有一个任何一个比前一个数字小的数字时,可以理解为这个数组分了一个空子数组旋转,相当于没有旋转,所以最小值还是数组中第一个数字。

要点:

  • 有序递增数组。
  • 子数组顺序不变。
  • 找出变化不符合规律的数字即为切分点。

代码

function minArray(numbers: number[]): number {
    if (numbers.length === 0) {
        return;
    } else {
        let result = numbers[0];
        for (let i = 1; i < numbers.length; i++) {
            if (numbers[i] < numbers[i - 1]) {
                result = numbers[i];
            }
        }
        return result;
    }
};

相关阅读


© 2022, 分享知识和生活,记录成长与感动。