数组旋转，来来来，走个K步~
前言
在前端算法面试中，数组是经常被问到的、使用到的。今天我们来看一道经典的前端基础面试题：【数组旋转K步】。
首先来看下这个题目，假定存在数组 arr = [1, 2, 3, 4, 5, 6, 7]，旋转 k = 3步，即数组末尾的元素依次进行挪动到数组的前面，即结果为 [5, 6, 7, 1, 2, 3, 4]。
题目其实不太难，我们借助这个题目来了解一下算法复杂度（时间复杂度、空间复杂度）以及数组中一些原生方法产生不同复杂度的问题
实现-方案1
思路很简单，每旋转一步，将数组末尾的最后一个元素取出，然后再插入到数组的最前面。
注意边界值问题考虑！！
/**
* @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方法只是将数组最后一个元素弹出，基本可以不考虑时间损耗。
整体的时间复杂度为
，即
，是不太理想的。
实现-方案2
我们一起来瞅瞅有没有一种更优的方式呢。
换个角度考虑下，从最终的结果来看，旋转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涉及数组元素的移动，是非常损耗性能的。
结语
以上就是胡哥今天给大家分享的内容，喜欢的小伙伴记得点赞、收藏呀，关注胡哥有话说，学习前端不迷路，欢迎多多留言交流...