算法：将一个数组旋转k步

题目

输入一个数组如 [1,2,3,4,5,6,7]，输出旋转 k 步后的数组。

• 旋转 1 步：就是把尾部的 7 放在数组头部前面，也就是 [7,1,2,3,4,5,6]
• 旋转 2 步：就是把尾部的 6 放在数组头部前面，也就是 [6,7,1,2,3,4,5]
• …

思路

思路1：将数组尾部的元素 pop，然后 unshift 到头部
思路2：将数组拆分成两段，然后通过 concat 拼接在一起

那么哪个是最优解呢？
遵循的原则：复杂度，在前端开发中重时间，轻空间。因为相应速度更重要，占内存的情况不那么重要。

代码

思路1

/*** 旋转数组 k 步 - 使用 pop 和 unshift* @param arr arr* @param k k* @returns arr*/
export function rotate1(arr: number[], k: number): number[] {const length = arr.lengthif (!k || length === 0) return arrconst step = Math.abs(k % length) // abs 取绝对值// O(n^2)for (let i = 0; i < step; i++) {const n = arr.pop()if (n != null) {arr.unshift(n) // 数组是一个有序结构，unshift 操作非常慢！！！ O(n)}}return arr
}

思路2

/*** 旋转数组 k 步 - 使用 concat* @param arr arr* @param k k*/export function rotate2(arr: number[], k: number): number[] {const length = arr.lengthif (!k || length === 0) return arrconst step = Math.abs(k % length) // abs 取绝对值// O(1)const part1 = arr.slice(-step) // O(1)const part2 = arr.slice(0, length - step)const part3 = part1.concat(part2)return part3
}

测试

// 功能测试
const arr = [1, 2, 3, 4, 5, 6, 7]
const arr1 = rotate2(arr, 3)
console.info(arr1)// 性能测试
const arr1 = []
for (let i = 0; i < 10 * 10000; i++) {arr1.push(i)
}
console.time('rotate1')
rotate1(arr1, 9 * 10000)
console.timeEnd('rotate1') // 885ms O(n^2)const arr2 = []
for (let i = 0; i < 10 * 10000; i++) {arr2.push(i)
}
console.time('rotate2')
rotate2(arr2, 9 * 10000)
console.timeEnd('rotate2') // 1ms O(1)

可以看到两种方式速度相差了百倍

测试用例

import { rotate1, rotate2 } from './array-rotate'describe('数组旋转', () => {it('正常情况', () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = 3const res = rotate2(arr, k)expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言})it('数组为空', () => {const res = rotate2([], 3)expect(res).toEqual([]) // 断言})it('k 是负值', () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = -3const res = rotate2(arr, k)expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言})it('k 是 0',  () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = 0const res = rotate2(arr, k)expect(res).toEqual(arr) // 断言})it('k 不是数字', () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = 'abc'// @ts-ignoreconst res = rotate2(arr, k)expect(res).toEqual(arr) // 断言})
})

执行 npx jest xxx.test.ts 即可

复杂度

思路1，时间复杂度为 O(n^2)，空间复杂度O(1)
思路2，时间复杂度为 O(1)，空间复杂度O(n)

思路1这里为什么是 O(n^2)，我们明明只有一次遍历？
答：数组是一个有序结构，unshift 操作非常慢

数组是连续的内存空间，就像这个教室的图，如果要把 F 同学放在前面（unshift操作），那么就得把 ABCDE挨个往后移动一位，所以这个操作是很慢的。但是 push、pop 操作不会，直接给后面添加/删除，前面同学不用动。