算法:将一个数组旋转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 操作不会,直接给后面添加/删除,前面同学不用动。