把一个数组旋转K步

题目如下：

• 输入一个数组，[1,2,3,4,5,6,7]，k = 3，即旋转3步，输出 [5,6,7,1,2,3,4]

思路一

• 使用 pop 和 unshift
  • 时间复杂度为 O(n^2)
  • 空间复杂度为 O(1)

export function rotate1(arr:number[],k:number):number[] {
  const length = arr.length
  if(!k || length === 0) return arr;
  const step = Math.abs(k%length);
  for(let i = 0;i < step;i++){
    const n = arr.pop()
    if(n != null) {
      arr.unshift(n) // 数组是一个有序结构，unshift操作非常慢 O(n)
    }
  }
  return arr
}

思路二

• 使用concat
  • 时间复杂度为 O(1)
  • 空间复杂度为 O(n)

export function rotate2(arr:number[],k:number):number[] {
  const length = arr.length
  if(!k || length === 0) return arr;
  const step = Math.abs(k%length);
  
  const part1 = arr.slice(-step);
  const part2 = arr.slice(0,length - step)
  const part3 = part1.concat(part2)
  return part3
}

性能测试

// 性能测试
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)

单元测试

/**
 * @description Array rotate test
 * @author sola-grj
 */

import { rotate1, rotate2 } from './array-rotate'

describe('数组旋转', () => {
    it('正常情况', () => {
        const arr = [1, 2, 3, 4, 5, 6, 7]
        const k = 3

        const 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 = -3

        const 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 = 0

        const res = rotate2(arr, k)
        expect(res).toEqual(arr) // 断言
    })

    it('k 不是数字', () => {
        const arr = [1, 2, 3, 4, 5, 6, 7]
        const k = 'abc'

        // @ts-ignore
        const res = rotate2(arr, k)
        expect(res).toEqual(arr) // 断言
    })
})