Skip to main content

轮转数组

给定一个整数数组 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]

简单做法：arr.splice(0, 1, arr.splice(arr.length -1, 1)), 执行k次

进阶做法： 要将数组中的元素向右轮转 k 个位置，可以采用多种方法，其中三次反转法是最高效且直观的解法，时间复杂度为 O(n)，空间复杂度为 O(1)。

方法思路​

  1. 处理 k 的有效性：由于轮转 k 次等价于轮转 k % n 次（n 为数组长度），因此先将 k 对 n 取模。
  2. 反转整个数组：将整个数组反转，使得后面的元素移到前面。
  3. 反转前 k 个元素：将数组的前 k 个元素反转，恢复这部分元素的顺序。
  4. 反转剩余元素：将数组的剩余元素反转，恢复这部分元素的顺序。

代码实现​

function rotate(nums, k) {
    const n = nums.length;
    k = k % n; // 处理 k 大于数组长度的情况
    
    // 反转整个数组
    reverse(nums, 0, n - 1);
    // 反转前 k 个元素
    reverse(nums, 0, k - 1);
    // 反转剩余元素
    reverse(nums, k, n - 1);
    
    return nums; // 题目要求原地修改，此返回仅为方便测试
}

// 辅助函数：反转数组中从 start 到 end 的元素
function reverse(nums, start, end) {
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]];
        start++;
        end--;
    }
}

示例分析​

以 nums = [1, 2, 3, 4, 5, 6, 7] 和 k = 3 为例：

  1. 处理 k：k = 3 % 7 = 3。
  2. 反转整个数组：[7, 6, 5, 4, 3, 2, 1]。
  3. 反转前 3 个元素：[5, 6, 7, 4, 3, 2, 1]。
  4. 反转剩余元素：[5, 6, 7, 1, 2, 3, 4]。

最终结果为 [5, 6, 7, 1, 2, 3, 4]，成功将元素向右轮转 3 个位置。

复杂度分析​

  • 时间复杂度：O(n)，三次反转操作均为 O(n)。
  • 空间复杂度：O(1)，仅需常数级额外空间。

其他解法对比​

  1. 暴力法：每次向右移动一位，重复 k 次。时间复杂度 O(n×k)，效率低。
  2. 额外数组法：创建新数组，将元素按正确位置复制。时间复杂度 O(n)，但空间复杂度 O(n)。
  3. 三次反转法：最优解，时间 O(n)，空间 O(1)。

正确性验证​

  • 当 k = 0 或 k = n：数组不变，三次反转后仍为原数组。
  • 当 k > n：通过取模处理，确保 k 在有效范围内。
  • 当 k 为任意值：三次反转操作能正确调整元素位置，逻辑严密。

三次反转法​

“三次反转法”是解决数组向右轮转k个位置的经典高效算法，核心思想是通过三次反转操作，在O(n)时间复杂度和O(1)空间复杂度内完成轮转，无需额外数组。

核心原理​

向右轮转k个位置，本质是将数组分为两部分：

  • 后k个元素（需要移到前面）；
  • 前n-k个元素（需要移到后面）。

三次反转的作用是：通过反转调整两部分的顺序，最终让后k个元素在前、前n-k个元素在后，且各自内部顺序保持不变。

详细步骤​

假设数组长度为n，需向右轮转k个位置：

  1. 处理k的有效性：
    轮转k次等价于轮转k % n次（因为轮转n次后数组会回到原始状态）。例如，n=5、k=7时，实际只需轮转7%5=2次。

  2. 第一次反转：反转整个数组
    将数组[a0, a1, ..., a(n-k-1), a(n-k), ..., a(n-1)]反转，得到：
    [a(n-1), ..., a(n-k), a(n-k-1), ..., a1, a0]。
    此时，原数组的后k个元素和前n-k个元素位置互换，但各自内部顺序是反转的。

  3. 第二次反转：反转前k个元素
    将第一步结果的前k个元素反转，得到：
    [a(n-k), ..., a(n-1), a(n-k-1), ..., a1, a0]。
    此时，原数组的后k个元素已恢复原始顺序，且位于数组前端。

  4. 第三次反转：反转剩余n-k个元素
    将第一步结果中剩余的n-k个元素反转，得到：
    [a(n-k), ..., a(n-1), a0, a1, ..., a(n-k-1)]。
    此时，原数组的前n-k个元素也恢复原始顺序，且位于数组后端，完成轮转。

示例演示​

以nums = [1,2,3,4,5,6,7]，k=3为例（n=7，k%n=3）：

  • 原始数组：[1,2,3,4,5,6,7]
  • 第一次反转（全数组）：[7,6,5,4,3,2,1]（整个数组反转）
  • 第二次反转（前3个）：[5,6,7,4,3,2,1]（前3个元素[7,6,5]反转后为[5,6,7]）
  • 第三次反转（剩余4个）：[5,6,7,1,2,3,4]（剩余元素[4,3,2,1]反转后为[1,2,3,4]）

最终结果符合“向右轮转3个位置”的预期。

代码实现（JavaScript）​

function rotate(nums, k) {
    const n = nums.length;
    if (n === 0) return; // 空数组无需处理
    k = k % n; // 处理k >= n的情况
    if (k === 0) return; // 轮转0次，直接返回

    // 反转数组的[start, end]区间（闭区间）
    const reverse = (start, end) => {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]]; // 交换元素
            start++;
            end--;
        }
    };

    reverse(0, n - 1); // 1. 反转整个数组
    reverse(0, k - 1); // 2. 反转前k个元素
    reverse(k, n - 1); // 3. 反转剩余n-k个元素
}

复杂度分析​

  • 时间复杂度：O(n)。三次反转操作共遍历数组2次（每次反转的总元素数为n），整体为O(n)。
  • 空间复杂度：O(1)。仅使用常数级额外空间（反转操作原地进行）。

边界情况验证​

  • 当k=0或k=n：数组不变（三次反转后仍为原数组）。
  • 当k > n：通过k%n处理后，等价于轮转有效次数，结果正确。
  • 当n=1：无论k为多少，数组始终不变（符合逻辑）。

三次反转法的巧妙之处在于利用反转的“对称性”，用最少的操作调整元素位置，是解决数组轮转问题的最优解，也是面试中的高频考点。