- 输入一个数组[1, 2, 3, 4, 5, 6, 7]
- k = 3, 即旋转3步
- 输出[5, 6, 7, 1, 2, 3, 4]
思路
- 1、把末尾的元素挨个 pop ,然后 unshift 到数组前面
- 2、把数组拆分,最后concat 拼接到一起
代码示例1
function rotate1 (arr: number[], k?:number): number[] {
const len = arr.length
if (!k || len === 0) return arr;
const step = Math.abs(k % len); // 取绝对值,防止step大于数组长度的情况
for (let i = 0; i < step; i++) {
const n = arr.pop()
if (typeof n !== "undefined") {
arr.unshift(n)
}
}
return arr;
}
代码示例2
function rotate2 (arr: number[], k?: number): number[] {
const len = arr.length
if (!k || len === 0) return arr;
const step = Math.abs( k % len); // 取绝对值,防止step大于数组长度的情况
const part1 = arr.slice(-step);
const part2 = arr.slice(0,len - step);
const part3 = part1.concat(part2)
return part3
}
关于 k % len
当k是字符串时,取余的结果是NaN
。在示例1中 i < NaN === false
, 在示例2中arr.slice(-NaN) === arr
。
功能测试
const res = rotate1([1, 2, 3, 4, 5, 6, 7],-3)
const res2 = rotate2 ([1, 2, 3, 4, 5, 6, 7],-3)
console.log(res) // [5, 6, 7, 1, 2, 3, 4]
console.log(res2) // [5, 6, 7, 1, 2, 3, 4]
JEST单元测试
describe('数组旋转', () => {
it('正常情况', () => {
const arr = [1, 2, 3, 4, 5, 6, 7]
const k = 3
const res = rotate1(arr,k)
expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言
})
it('数组为空', () => {
const res = rotate1([],3)
expect(res).toEqual([]) // 断言
})
it('k 是负值', () => {
const arr = [1, 2, 3, 4, 5, 6, 7]
const k = -3
const res = rotate1(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 = 0
const res = rotate1(arr,k)
expect(res).toEqual(arr) // 断言
})
it('k 不是数值', () => {
const arr = [1, 2, 3, 4, 5, 6, 7]
const k = 'abc'
@ts-ignore
const res = rotate1(arr,k)
expect(res).toEqual(arr) // 断言
})
})
性能测试
const testArr1 = []
for(let i = 0; i < 10 * 10000; i++){
testArr1.push(i)
}
console.time('rotate1')
rotate1(testArr1,9 * 10000)
console.timeEnd('rotate1')
const testArr2 = []
for(let i = 0; i < 10 * 10000; i++){
testArr2.push(i)
}
console.time('rotate2')
rotate2(testArr2,9 * 10000)
console.timeEnd('rotate2')
结果:
rotate1: 3.611s
rotate2: 1.147ms
思路2 性能 远超思路1
复杂度分析
- 思路1: 时间复杂度O(n ^2), 空间复杂度O(1)
- 思路2:时间复杂度O(1),空间复杂度O(n)
数组是一个连续的内存空间,unshift操作是一个有序的操作,相当于对数组进行了一次遍历,所以非常慢!!!
所以思路1的时间复杂度不是O(n)而是O(n ^ 2)!
正确选择答案
- 选择思路2:拆分数组,最后concat拼接,返回
- 时间复杂度O(1),足够快
- 空间复杂度O(n),对于前端(重时间,轻空间)可以接受