前言
在前端算法面试中，数组是经常被问到的、使用到的。今天我们来看一道经典的前端基础面试题：【数组旋转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本身，所以空间复杂度是O(n)O(n)O(n)，是可接受的。
时间复杂度：
在该函数中有一层for循环，此处时间复杂度是O(n)O(n)O(n);
同时在函数的内部中涉及到了数组元素的移动 unshift。大家都知道数组在内存中是以连续内存的方式进行存储的，以数组arr = [1, 2, 3, 4, 5, 6, 7]为例，如果想将元素7移动到数组的最前面，需要依次将数组元素6、5、4、3、2、1依次向后移动，然后将7插入，所以unshift方法的时间复杂度是O(n)O(n)O(n)。pop方法只是将数组最后一个元素弹出，基本可以不考虑时间损耗。
整体的时间复杂度为O(n)∗O(n)O(n) * O(n)O(n)∗O(n)，即O(n2)O(n^2)O(n2)，是不太理想的。
实现-方案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的实现多声明了一个变化，但从量级上来说，还是一个O(n)O(n)O(n)的复杂度，是可接受的。
时间复杂度：
在该算法中没有循环，只是单纯的调用了slice方法，截取了数组元素，同时也没有影响数组arr本身，所以可以将该算法视为常量级的时间复杂度O(1)O(1)O(1)。
有可能会有小伙伴对slice操作视为O(1)O(1)O(1)时间复杂度有疑问。在JS中，数组在内存中是连续存储的，也就是说我们能够根据索引，快速定位到元素，进而执行。这个操作是非常快速的，视为常量级O(1)O(1)O(1)
方案比较：
我们在谈论时间复杂度和空间复杂度时讨论的是一个量级问题，不是一个绝对值问题。也就是说随着数组arr的长度越大，旋转的k值越大，时间复杂度为O(1)O(1)O(1)方案2的性能要远远的比时间复杂度为O(n2)O(n^2)O(n2)的方案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");
结果上图：
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");
结果上图：
注：不同配置的电脑在上述测试中，结果数值是存在差异性的。
效果还是非常明显的啦，二者对比，方案2要远胜于方案1
小课堂
在数组中方法的操作中，注意数组的方法 unshift、shift、splice涉及数组元素的移动，是非常损耗性能的。
