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

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

数据结构与算法 · 把一个数组旋转k步

一、问题描述

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

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

二、for + unshift + pop 实现

代码演示：

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
}

算法复杂度

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

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

三、slice + concat 实现（`推荐`）

代码演示

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

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')

<div> <button style='padding: 10px 20px; color: #00b1fb;' class='rotate-btn' onclick='run()'>运行</button> <br> <b>rotate1 run time：</b> <span style='color: red;' class='rotate1-ms'>0</span> <hr> <b>rotate2 run time：</b> <span style='color: red;' class='rotate2-ms'>0</span> <hr> </div> <script> function rotate1(arr, k) { 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

}

function rotate2(arr, k) { 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)) }

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

let s1 = performance.now()
rotate1(list1, 10 * 10000)
document.querySelector('.rotate1-ms').innerText = performance.now() - s1 + ' ms'

let s2 = performance.now()
rotate2(list2, 10 * 10000)
document.querySelector('.rotate2-ms').innerText = performance.now() - s2 + ' ms'

} </script>

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

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

《数据结构与算法》系列

欢迎访问：天问博客