在前端算法面试中,数组是经常被问到的、使用到的。今天我们来看一道经典的前端基础面试题:【数组旋转K步】。
首先来看下这个题目,假定存在数组 arr = [1, 2, 3, 4, 5, 6, 7]
,旋转 k = 3
步,即数组末尾的元素依次进行挪动到数组的前面,即结果为 [5, 6, 7, 1, 2, 3, 4]
。
题目其实不太难,我们借助这个题目来了解一下算法复杂度(时间复杂度、空间复杂度)以及数组中一些原生方法产生不同复杂度的问题
思路很简单,每旋转一步,将数组末尾的最后一个元素取出,然后再插入到数组的最前面。
注意边界值问题考虑!!
/**
* @method rotate
* @description 数组渲染K步
* @param arr number[]
* @param k number
*/
function rotate (arr: number[], k: number): number[] {
const len = arr.length;
// 此处考虑边界值问题
// 数组为空
if (len === 0) {
return arr;
}
// K步 - K的取值
// 如果是负值直接给处理为正数,取绝对值
// 如果是 k > len 即大于数组长度时,取余数
// 如 arr 的 len === 5,设置 k === 9,其实相当于将数组旋转一圈之后,再走了 k % len === 4 步
const step = Math.abs(k % len);
for (let i = 0; i < step; i++) {
// 每次取出最后一个元素
const lastEle = arr.pop();
// 将取出的元素,放入到数组的最前面
// 因为pop方法可能会抛出一个undefined值,实际我们已经约束了,不会出现这个情况,但是ts会进行检测,所以这个位置添加了@ts-ignore
// @ts-ignore
arr.unshift(lastEle);
}
return arr;
}
是骡子是🐴拉出来遛遛~~~
const arr = [1, 2, 3, 4, 5, 6, 7];
console.log(rotate(arr, 3)) // [5, 6, 7, 1, 2, 3, 4]
通过该方案结果是有了,那这个是一个非常优秀的方案吗?我们来分析下该实现的时间复杂度和空间复杂度。
空间复杂度:
在该函数中没有新产生一个空间对象,还是数组arr本身,所以空间复杂度是
,是可接受的。
时间复杂度:
在该函数中有一层for循环,此处时间复杂度是
;
同时在函数的内部中涉及到了数组元素的移动 unshift
。大家都知道数组在内存中是以连续内存的方式进行存储的,以数组arr = [1, 2, 3, 4, 5, 6, 7]
为例,如果想将元素7
移动到数组的最前面,需要依次将数组元素6、5、4、3、2、1
依次向后移动,然后将7
插入,所以unshift
方法的时间复杂度是
。pop
方法只是将数组最后一个元素弹出,基本可以不考虑时间损耗。
整体的时间复杂度为
,即
,是不太理想的。
我们一起来瞅瞅有没有一种更优的方式呢。
换个角度考虑下,从最终的结果来看,旋转k
步,即将数组最后的k
个元素取出,与剩余的其他元素进行拼接,返回最终结果,从代码上表示为:[5, 6, 7].concat([1, 2, 3, 4])
。
各位小伙伴,解题思路已经转变到如何从数组arr
中截取出[5, 6, 7]
和[1, 2, 3, 4]
,很简单,数组的slice
方法解决问题。
上代码
/**
* @method rotate2
* @description 数组渲染K步
* @param arr number[]
* @param k number
*/
function rotate2 (arr: number[], k: number) {
// 获取数组长度
const len = arr.length;
// 同样的边界值判断
if (len === 0) {
return arr;
}
// 取余、取绝对值
// 逻辑同上
const step = Math.abs(k % len);
// slice调用时传递负数,为取出最后的step个元素
const p1 = arr.slice(-step);
// 取出前面的0 至 len-step个元素
const p2 = arr.slice(0, len - step);
// 拼接新数组返回
return p1.concat(p2);
}
我们来看下这个实现的时间复杂度和空间复杂度。
空间复杂度:
虽然该算法实现中,返回了一个新数组,看起来似乎比方案1的实现多声明了一个变化,但从量级上来说,还是一个
的复杂度,是可接受的。
时间复杂度:
在该算法中没有循环,只是单纯的调用了slice
方法,截取了数组元素,同时也没有影响数组arr
本身,所以可以将该算法视为常量级的时间复杂度
。
有可能会有小伙伴对slice
操作视为
时间复杂度有疑问。在JS中,数组在内存中是连续存储的,也就是说我们能够根据索引,快速定位到元素,进而执行。这个操作是非常快速的,视为常量级
方案比较:
我们在谈论时间复杂度和空间复杂度时讨论的是一个量级
问题,不是一个绝对值问题。也就是说随着数组arr
的长度越大,旋转的k
值越大,时间复杂度为
方案2的性能要远远的比时间复杂度为
的方案1优秀的多。
我们可以使用console.time()、console.timeEnd()
,来进行性能的测试。
我们依次使用一个10W、100W长度的数组,旋转100步、1000步,来对比二者的性能。
定义一个可以生成指定长度数组的方法:
/**
* @method makeArr
* @description 根据传入的长度len生成指定长度的数组
* @param len number 指定的数组长度
*/
function makeArr(len: number): number[] {
const arr: number[] = [];
for (let i = 0; i < len; i++) {
arr.push(i);
}
return arr;
}
10W条数据比较:
// 指定长度10W
const len = 10 * 10000;
// 第一个方案
const arr = makeArr(len);
console.time("rotate1");
const res = rotate(arr, 100);
console.timeEnd("rotate1");
// 第二个方案
const arr2 = makeArr(len);
console.time("rotate2");
const res2 = rotate2(arr2, 100);
console.timeEnd("rotate2");
结果上图:
image.png
100W条数据比较:
// 指定长度10W
const len = 100 * 10000;
// 第一个方案
const arr = makeArr(len);
console.time("rotate1");
const res = rotate(arr, 1000);
console.timeEnd("rotate1");
// 第二个方案
const arr2 = makeArr(len);
console.time("rotate2");
const res2 = rotate2(arr2, 1000);
console.timeEnd("rotate2");
结果上图:
image.png
注:不同配置的电脑在上述测试中,结果数值是存在差异性的。
效果还是非常明显的啦,二者对比,方案2要远胜于方案1
在数组中方法的操作中,注意数组的方法 unshift
、shift
、splice
涉及数组元素的移动,是非常损耗性能的。
以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞
、收藏
呀,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流...