【数据结构与算法】(3)：把一个数组旋转k步

使用 JavaScript 如何将一个 数组旋转k步 ，我将使用 for + unshift + pop 和 slice + concat 两种方法来实现，并对其算法复杂度和性能进行分析对比。

一、问题描述

给定一个数组和一个非负整数k，要求将数组向右旋转k步。 例如：

• input：[1, 2, 3, 4, 5, 6, 7] ， k = 3
• output：[5, 6, 7, 1, 2, 3, 4]

二、for + unshift + pop 实现

1. 代码演示：

function rotate1(arr: number[], k:number):number[] {
  const len = arr.length
  if (!k || len===0) return arr
  const step = Math.abs(k % len)

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

2. 算法复杂度

因为 数组是一个有序结构，连续的内存空间 ，unshift 操作相当于是做了一次循环 O(n)，再加上在 for 循环中使用，所以其算法复杂度就是：

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)

三、slice + concat 实现 （推荐）

1. 代码演示

function rotate2(arr: number[], k:number):number[] {
  const len = arr.length
  if (!k || len===0) return arr
  const step = Math.abs(k % len)
  return arr.slice(0, len-step).concat(arr.slice(-step))  // O(1)
}

2. slice 不改变原数据，相当于浅拷贝，所以其算法复杂度就是：

• 时间复杂度 O(n)
• 空间复杂度 O(n)

四、性能测试

使用上述两种方法分别对以下数组和 k 进行性能测试。
input：[0, 1, 2, 3, 4, 5, .... , 200000] ，k=100000

代码演示：

const list1 = []
for (let i = 0; i < 20 * 10000; i++) {
  list1.push(i)
}
const list2 = JSON.parse(JSON.stringify(list1))

console.time('rotate1')
rotate1(list1, 10 * 10000)
console.timeEnd('rotate1')

console.time('rotate2')
rotate2(list2, 10 * 10000)
console.timeEnd('rotate2')

运行


rotate1 run time： 0

---

rotate2 run time： 0

---

通过运行得知 rotate1 方法远不如 rotate2 方法的执行效率。

总结：数据量越大越能突显算法的重要性。

---

《数据结构与算法》系列

1. 什么是算法复杂度
2. 堆(heap)、栈(stack)、队列(queue)
3. 把一个数组旋转k步
4. 判断字符串是否括号匹配
5. 数组、栈、链表、队列结构与对比
6. 用两个栈实现一个队列
7. 反转单向链表
8. 用链表实现队列
9. 二分查找
10. 查找两数之和

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-11
最后更新： 2023-07-20
本文标题： 【数据结构与算法】(3)：把一个数组旋转k步
本文链接： https://www.tiven.cn/p/12d6f2da/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！