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