189. 轮转数组

题目链接：https://leetcode.cn/problems/rotate-array/

代码

/**
 * 189. 轮转数组
 * https://leetcode.cn/problems/rotate-array/
 Do not return anything, modify nums in-place instead.
 */

// 可能超时
function rotate(nums: number[], k: number): void {
    const times = k % nums.length;
    for (let i = 1; i <= times; i++) {
        const num = nums.pop()!;
        nums.unshift(num);
    }
}

// 利用splice
function rotate2(nums: number[], k: number): void {
    const n = nums.length;
    k %= n;
    if (k === 0) return;
    // splice(开始操作的索引，要删除多少个，要插入的新元素)
    // nums.splice(n - k)为后k个元素
    nums.splice(0, 0, ...nums.splice(n - k));
}

思路

方法一：pop + unshift（可能超时）

每次将数组最后一个元素弹出，然后插入到数组开头，重复 k 次。

• 时间复杂度 $O(n\times k)$，当 k 很大时可能超时
• 空间复杂度 $O(1)$

方法二：splice（推荐）

利用 splice 方法一次性完成操作：

1. 先对 k 取模，处理 k 大于数组长度的情况
2. 使用 nums.splice(n - k) 获取后 k 个元素
3. 使用 nums.splice(0, 0, ...) 将这些元素插入到数组开头

• 时间复杂度 $O(n)$
• 空间复杂度 $O(k)$（splice 会创建新数组）

注意：splice(开始索引, 删除个数, 插入元素...) 的用法，splice(n - k) 会返回后 k 个元素并删除它们，然后通过 splice(0, 0, ...) 插入到开头。