将一个数组旋转 k 步

实现目标

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

解析思路

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

代码实现

复杂度分析

• 思路 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)