算法题：将一个数组旋转 k 步都有哪些方法并分析复杂度

/**
* @description Array rotate
* @author lsr
*/
/**
* 将一个数组旋转 k 步 - pop unshift
* @param arr arr
* @param k k
* @returns arr
*/
export function rotate1(arr: number[], k: number): number[] {
const length = arr.length
if (!k || length === 0) return arr
const step = Math.abs(k)
if (k > arr.length) return arr
// O(n^2)
for (let i = 0; i < step; i++) {
const n = arr.pop()
if (n != null) arr.unshift(n) // 数组是有序结构 unshift 操作非常慢(On)
}
return arr
}
/**
* 将一个数组旋转 k 步 - concat slice
* @param arr arr
* @param k k
* @returns arr
*/
export function rotate2(arr: number[], k: number): number[] {
const length = arr.length
if (!k || length === 0) return arr
const step = Math.abs(k)
if (k > arr.length) return arr
const part1 = arr.slice(0, length - step)
const part2 = arr.slice(-step)
const newArr = part2.concat(part1)
return newArr
}
// 功能测试
// console.log(rotate1([1, 2, 3, 4, 5, 6, 7], 3))
// console.log(rotate2([1, 2, 3, 4, 5, 6, 7], 3)) // [5, 6, 7, 1, 2, 3, 4]
// 性能测试
// const arr1 = []
// for (let i = 0; i < 10 * 10000; i++) {
//
arr1.push(i)
// }
// console.time('rotate1')
// rotate1(arr1, 90 * 1000)
// console.timeEnd('rotate1') // 888ms O(n^2)
// const arr2 = []
// for (let i = 0; i < 10 * 10000; i++) {
//
arr2.push(i)
// }
// console.time('rotate2')
// rotate2(arr2, 90 * 1000)
// console.timeEnd('rotate2') // 0.47ms O(n1)

单元测试

import { rotate1, rotate2 } from '@/01-algorithm/array-rotate'
describe('将一个数组旋转 k 步', () => {
it('正常情况', () => {
const arr = [1, 2, 3, 4, 5, 6, 7]
const k = 3
const result = [5, 6, 7, 1, 2, 3, 4]
expect(rotate2(arr, k)).toEqual(result)
})
it('空数组', () => {
const k = 3
expect(rotate2([], k)).toEqual([])
})
it('k 大于数组的长度', () => {
const arr = [1, 2, 3, 4, 5, 6, 7]
const k = 100
const result = [1, 2, 3, 4, 5, 6, 7]
expect(rotate2(arr, k)).toEqual(result)
})
it('k 是负值', () => {
const arr = [1, 2, 3, 4, 5, 6, 7]
const k = -3
const result = [5, 6, 7, 1, 2, 3, 4]
expect(rotate2(arr, k)).toEqual(result)
})
})

复杂度分析

• rotate1：时间复杂度O(n^2)，空间复杂度O(1)
• rotate2：时间复杂度O(1)，空间复杂度O(n)

注：前端是重时间轻空间的，而且空间是O(n)的复杂度是非常可以接受的

划重点

• 注意算法时间复杂度，前端重时间轻空间
• 识破内置 API 的时间复杂度（如 unshift）
• 单元测试，考虑参数非法情况，提升代码健壮性

最后

以上就是小巧店员为你收集整理的算法题：将一个数组旋转 k 步都有哪些方法并分析复杂度的全部内容，希望文章能够帮你解决算法题：将一个数组旋转 k 步都有哪些方法并分析复杂度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。