Vue.js

Appearance

On this page

实战：旋转数组 ​

这道题有一个非常巧妙的解法：三次翻转。

这个技巧在很多数组和字符串题目中都会用到，值得记住。

题目描述 ​

LeetCode 189. 旋转数组

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

示例：

输入：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]

进阶：你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

题目分析 ​

关键点：

  1. 向右轮转：每个元素向右移动 k 位，超出末尾的回到开头
  2. 原地修改：不能创建新数组
  3. k 可能大于数组长度：需要取模处理

先想一下：轮转 k 位之后，数组变成什么样？

原数组:  [1, 2, 3, 4, 5, 6, 7]
         |← 前 n-k 个 →| |← 后 k 个 →|

轮转后:  [5, 6, 7, 1, 2, 3, 4]
         |← 后 k 个 →| |← 前 n-k 个 →|

就是把后 k 个元素移到前面。

解法一：使用额外数组 ​

最直观的方法：创建一个新数组，每个元素放到它应该在的位置。

javascript
function rotate(nums, k) {
    const n = nums.length;
    k = k % n;  // 处理 k > n 的情况
    
    const temp = new Array(n);
    for (let i = 0; i < n; i++) {
        // 元素 i 移动到 (i + k) % n 的位置
        temp[(i + k) % n] = nums[i];
    }
    
    // 复制回 nums
    for (let i = 0; i < n; i++) {
        nums[i] = temp[i];
    }
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

简单直观，但用了额外空间。能不能 O(1) 空间？

解法二：三次翻转（最优解） ​

这是一个非常巧妙的方法。

观察一下目标数组：

原数组: [1, 2, 3, 4 | 5, 6, 7]
              前 4 个   后 3 个

目标:   [5, 6, 7 | 1, 2, 3, 4]
         后 3 个    前 4 个

如果我们：

  1. 先把整个数组翻转
  2. 再把前 k 个翻转
  3. 再把后 n-k 个翻转

看看会发生什么：

原数组: [1, 2, 3, 4, 5, 6, 7]

Step 1 - 整体翻转:
[7, 6, 5, 4, 3, 2, 1]

Step 2 - 翻转前 k=3 个:
[5, 6, 7, 4, 3, 2, 1]

Step 3 - 翻转后 n-k=4 个:
[5, 6, 7, 1, 2, 3, 4] ✓

完美！

为什么这样做是对的？

整体翻转后，原来的后 k 个跑到了前面，但顺序是反的。原来的前 n-k 个跑到了后面，顺序也是反的。

分别把它们翻转回来，就得到了正确的结果。

javascript
function rotate(nums, k) {
    const n = nums.length;
    k = k % n;
    
    // 辅助函数：翻转数组的 [start, end] 区间
    const reverse = (start, end) => {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            start++;
            end--;
        }
    };
    
    reverse(0, n - 1);     // 翻转整个数组
    reverse(0, k - 1);     // 翻转前 k 个
    reverse(k, n - 1);     // 翻转后 n-k 个
}

复杂度分析：

  • 时间复杂度：O(n)——每个元素翻转两次，总共 2n 次操作
  • 空间复杂度：O(1)——只用了几个变量

这是最优解。代码简洁，空间最优。

解法三：环状替换 ​

还有一种方法：直接把每个元素放到它应该在的位置。

问题是，放过去之后，原来在那个位置的元素怎么办？

答案是：把它也移到它应该在的位置。这样一直移下去，最终会回到起点，形成一个"环"。

javascript
function rotate(nums, k) {
    const n = nums.length;
    k = k % n;
    let count = 0;  // 已移动的元素数
    
    for (let start = 0; count < n; start++) {
        let current = start;
        let prev = nums[start];
        
        do {
            const next = (current + k) % n;
            [nums[next], prev] = [prev, nums[next]];
            current = next;
            count++;
        } while (current !== start);
    }
}

这个方法比较难理解，在某些情况下（k 和 n 有公约数时）需要多个环才能覆盖所有元素。

面试中推荐使用三次翻转法，更容易解释。

三种方法对比 ​

方法时间复杂度空间复杂度特点
额外数组O(n)O(n)最简单直观
三次翻转O(n)O(1)空间最优，推荐
环状替换O(n)O(1)巧妙但较难理解

常见错误 ​

  1. 没有处理 k > n
javascript
// 错误：k=10, n=7 时会出问题
k = k % n;  // 必须加这一行
  1. 翻转边界错误
javascript
// 正确的边界
reverse(0, k - 1);     // 前 k 个是 [0, k-1]
reverse(k, n - 1);     // 后 n-k 个是 [k, n-1]
  1. k = 0 的情况

当 k = 0 或 k = n 时，数组不需要变化。k % n = 0 会自动处理这种情况。

相关题目 ​

  • 61. 旋转链表：链表版本
  • 186. 反转字符串中的单词 II：也用到翻转技巧

本章小结 ​

这一章我们学习了三次翻转技巧：

  1. 目标：把后 k 个元素移到前面
  2. 方法：整体翻转 → 翻转前 k 个 → 翻转后 n-k 个
  3. 为什么有效：翻转可以"交换"两部分的位置

记住这个技巧。当你需要"把数组的一部分移到另一个位置"时，翻转往往是最优雅的解法。

下一章，我们来看「加一」这道题。

在 GitHub 上编辑此页