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


字数:677 阅读时长:3分钟 阅读:85

使用 JavaScript 如何将一个 数组旋转k步 ,我将使用 for + unshift + popslice + 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 实现

  1. 代码演示:
1
2
3
4
5
6
7
8
9
10
11
12
13
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
}
  1. 算法复杂度

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

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

三、slice + concat 实现 (推荐

  1. 代码演示
1
2
3
4
5
6
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)
}
  1. slice 不改变原数据,相当于浅拷贝,所以其算法复杂度就是:
  • 时间复杂度 O(n)
  • 空间复杂度 O(n)

四、性能测试

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

代码演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
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 许可协议进行许可。转载请注明出处!
欢迎留言,提问 ^_^
个人邮箱: tw.email@qq.com
notification icon
博客有更新,将会发送通知给您!