将一个数组旋转 k 步

实现目标

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

解析思路

思路 1：把末尾 pop 出来，然后 unshift 到前面
思路 2：把数组拆分，然后 contact 拼接在一起

代码实现

// 思路1

function rotate1(arr: number[], k: number): number[] {
  const length = arr.length
  if (!k || length === 0) return arr
  const step = Math.abs(k & length) // k可能大于length 所以取余，绝对值

  for (let i = 0; i < step; i++) {
    const n = arr.pop()
    if (n != null) {
      arr.unshift(n)
    }
  }

  return arr
}

// 思路2
function rotate2(arr: number[], k: number): number[] {
  const length = arr.length
  if (!k || length === 0) return arr
  const step = Math.abs(k & length) // k可能大于length 所以取余，绝对值

  const part1 = arr.slice(-step)
  const part2 = arr.slice(length - step)
  const part3 = part1.concat(part2)

  return part3
}

// 测试用例 - 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])
  })
});

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])
  })
});


// 性能测试
const arr1 = []
const arr2 = []
for (let i = 1; i <= 100000; i++) {
  arr1.push(i)
  arr2.push(2)
}

console.log('rotate1用时')
console.time('rotate1')
rotate1(arr1, 9 * 10000)
console.timeEnd('rotate1')

console.log('rotate2用时')
console.time('rotate2')
rotate2(arr2, 9 * 10000)
console.timeEnd('rotate2')

复杂度分析

思路 1：时间复杂度 O(n^2)，空间复杂度 O(1)
思考？为啥时间复杂度是 O(n^2)，这里涉及的几个知识点
- for 循环时间复杂度 O(n)
- 数组是有序的内存存储，unshift 是直接操作原数组插入元素，数组内部所有元素位置都在调整，时间复杂度 O(n)
- 所以最终就是 O(n^2)
思路 2：时间复杂度 O(1), 空间复杂度 O(n) slice 不直接操作原数组，相对于复制，所以时间复杂度 O(1)

将一个数组旋转 k 步 ​

将一个数组旋转 k 步