【数据结构与算法】题目1:将一个数组旋转 k 步

题目

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

实现思路

1. 利用数组方法把末尾的元素挨个 pop， 然后 unshift 到数组前面（在原数组基础上操作）：时间复杂度O(n^2)，空间复杂度O(1)。需要注意的是数组是一个有序结构、连续的内存空间。数组的shift unshift splice 操作都会非常慢。
2. 把数组拆分，再 concat 拼接在一起（生成新的数组）：时间复杂度O(1)，空间复杂度O(n)。slice 不会改变原数组和 unshift 不同

array-rotate.ts 

// 思路 1 实现- 使用 pop unshift方法
export function rotate1(arr: number[], k: number): number[] {
    const length = arr.length
    if(!k || length === 0) return arr
    const step = Math.abs(k % length) // abs 取绝对值
    // 时间复杂度 O(n^2)
    // 空间复杂度 O(1)
    for (let i = 0; i < step; i++) {
        const n = arr.pop()
        if (n != null) {
            arr.unshift(n) // 数组是一个有序结构、连续的内存空间，unshift 操作非常慢
        }
    }
    return arr
}

// 思路 2- 使用 concat
export function rotate2(arr: number[], k:number): number[]{
    const length = arr.length
    if(!k || length === 0) return arr
    const step = Math.abs(k % length) // abs 取绝对值 
     
    // 时间复杂度 O(1)
    // 空间复杂度 O(n)
    const part1 = arr.slice(-step)
    const part2 = arr.slice(0, length - step)
    return part1.concat(part2)
}

// 性能测试
const arr1 = []
for(let i = 0; i < 10 * 10000; i++) {
    arr1.push(i)
}

console.time('rotate1')
rotate1(arr1, 9 * 10000)
console.timeEnd('rotate1') // 885ms O(n^2)

const arr2 = []
for (let i = 0; i < 10 * 10000; i++) {
    arr2.push(i)
}
console.time('rotate2')
rotate2(arr2, 9 * 10000)
console.timeEnd('rotate2') // 1ms O(1)

array-rotate.test.ts 

import { rotate1, roteate2 } from './array-rotate

describe('数组旋转', () => {
    it('正常情况', () => {
        const arr = [1,2,3,4,5,6,7]
        const k = 3
        const res = rotate1(arr, k)
        expect(res).toEqual([5,6,7,1,2,3,4]) // 断言
    })
    it('数组为空', () => {
        const arr = []
        const k = 3
        const res = rotate1(arr, k)
        expect(res).toEqual([])
    })
    it('k 是负值', () => {
        const arr = [1,2,3,4,5,6,7]
        const k = -3
        const res = rotate1(arr, k)
        expect(res).toEqual([5,6,7,1,2,3,4])
    })
    it('k 是0', () => {
        const arr = [1,2,3,4,5,6,7]
        const k = 0
        const res = rotate1(arr, k)
        expect(res).toEqual(arr)
    })

    it('k 不是数字', () => {
        const arr = [1,2,3,4,5,6,7]
        const k = 'abc'

        //@ts-ignore
        const res = rotate1(arr, k)
        expect(res).toEqual(arr)
    })
})