【LeetCode热题100道笔记】轮转数组

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

思考一：使用额外数组

直接计算每个元素旋转后的新位置，借助额外数组存储结果后再复制回原数组。

算法过程

1. 计算有效旋转步数 k = k % n（n为数组长度）
2. 创建与原数组等长的新数组
3. 遍历原数组，将每个元素 nums[i] 放入新数组的 (i + k) % n 位置
4. 将新数组元素复制回原数组

复杂度：时间O(n)，空间O(n)（额外数组占用）

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const n = nums.length;
    k = k % n;
    if (k === 0) return;
    
    const temp = [...nums]; // 创建原数组副本
    for (let i = 0; i < n; i++) {
        // 计算旋转后位置：原索引i的元素移到(i + k) % n
        nums[(i + k) % n] = temp[i];
    }
};

思考二：环形替换

核心思路：从起始位置开始，将元素依次移动到旋转后的目标位置，形成闭环后切换到下一个未处理的位置，直到所有元素都被移动。

算法过程

1. 计算有效旋转步数 k = k % n，若k为0则返回
2. 初始化计数器 count = 0（记录已处理元素数量）
3. 从索引0开始循环：
   • 记录当前位置 current 和该位置的元素 prev
   • 计算目标位置 next = (current + k) % n
   • 交换 prev 与目标位置元素，更新 current 为 next
   • 重复上述步骤，直到回到起始位置（形成闭环）
   • 计数器加1，若未处理完所有元素则从下一个索引继续

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const n = nums.length;
    k = k % n;
    if (k === 0) return;
    
    let count = 0; // 已处理的元素数量
    for (let start = 0; count < n; start++) {
        let current = start;
        let prev = nums[start];
        do {
            const next = (current + k) % n;
            [prev, nums[next]] = [nums[next], prev]; // 交换元素
            current = next;
            count++;
        } while (current !== start); // 回到起点时结束当前环
    }
};

思考三：反转数组

将数组向右旋转k步，可通过三次反转操作实现原地修改：先反转整个数组，再分别反转前k个元素和剩余元素，以此等价于直接旋转的效果，避免使用额外空间。

算法过程

1. 计算有效旋转步数：k = k % 数组长度（处理k大于数组长度的情况），若k为0则无需旋转
2. 第一次反转：将整个数组从索引0到末尾反转
3. 第二次反转：将数组前k个元素（索引0到k-1）反转
4. 第三次反转：将数组剩余元素（索引k到末尾）反转

通过三次局部反转，最终实现数组整体向右旋转k步的效果，时间复杂度O(n)，空间复杂度O(1)。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const len = nums.length;
    const count = k % len;
    if (count === 0) return;
    reverse(nums, 0, len-1);
    reverse(nums, 0, count-1);
    reverse(nums, count, len-1);
};

function reverse(nums, begin, end) {
    while (begin < end) {
        [nums[begin], nums[end]] = [nums[end], nums[begin]];
        begin++;
        end--;
    }
}