【前端算法】将一个数组旋转K步

• 输入一个数组[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），对于前端（重时间，轻空间）可以接受