Sign in Subscribe
算法

轮转数组

loser

• 7 min read
Share

给定一个整数数组 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 <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^5

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

解法一（辅助数组）：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        vector<int> temp(n);

        for (int i = 0; i < n; i++)
        {
            temp[(i + k) % n] = nums[i];
        }

        nums = temp;
    }
};

解法二（三次反转）：

class Solution {
public:
    void reverseRange(vector<int>& nums, int left, int right) {
        while (left < right)
        {
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        reverseRange(nums, 0, n - 1);
        reverseRange(nums, 0, k - 1);
        reverseRange(nums, k, n - 1);
    }
};

也可以直接使用标准库 reverse：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

解法三（环状替换）：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        int count = 0;

        for (int start = 0; count < n; start++)
        {
            int current = start;
            int prev = nums[start];

            do
            {
                int next = (current + k) % n;
                swap(nums[next], prev);
                current = next;
                count++;
            } while (current != start);
        }
    }
};

解法四（标准库 rotate）：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        std::rotate(nums.begin(), nums.end() - k, nums.end());
    }
};

核心思想

向右轮转 k 个位置，本质上是让每个元素移动到新的下标。

对于原数组下标 i 的元素，向右移动 k 位后，它的新下标是：

(i + k) % n

其中 n = nums.size()。

取模是为了处理越过数组末尾的情况。

例如：

nums = [1,2,3,4,5,6,7], k = 3

原下标 0 的元素 1 会去到：

(0 + 3) % 7 = 3

原下标 5 的元素 6 会去到：

(5 + 3) % 7 = 1

所以数组尾部的元素会被轮转到数组前面。

为什么要先处理 k %= n

数组长度是 n。

如果向右轮转 n 次，数组会回到原样。

所以轮转 k 次和轮转：

k % n

次的结果完全相同。

例如数组长度为 7，轮转 10 次等价于轮转：

10 % 7 = 3

次。

因此所有解法开头都要先写：

k %= n;

这样既可以减少无意义操作，也能避免下标计算出错。

解法一：辅助数组

辅助数组是最直接的做法。

根据轮转公式：

新下标 = (旧下标 + k) % n

我们开一个新数组 temp，把原数组每个位置的元素放到它轮转后的新位置：

temp[(i + k) % n] = nums[i];

最后再把 temp 赋值回 nums。

这个方法最容易理解，因为它完全按照轮转定义来做。

缺点是需要额外 O(n) 空间。

解法二：三次反转

三次反转是最推荐掌握的原地解法。

把原数组分成两段：

  • A：前 n - k 个元素
  • B：后 k 个元素

原数组可以写成：

A B

向右轮转 k 位之后，目标是：

B A

三次反转的过程是：

  1. 反转整个数组。
  2. 反转前 k 个元素。
  3. 反转后 n - k 个元素。

用符号表示：

原数组：

A B

整体反转：

reverse(B) reverse(A)

再分别反转两段：

B A

所以三次反转就能得到右轮转后的结果。

三次反转为什么正确

假设：

nums = [1,2,3,4,5,6,7], k = 3

那么：

A = [1,2,3,4]

B = [5,6,7]

目标结果是：

B A = [5,6,7,1,2,3,4]

第一次反转整个数组：

[1,2,3,4,5,6,7]

变成：

[7,6,5,4,3,2,1]

这其实就是：

reverse(B) reverse(A)

也就是：

[7,6,5] [4,3,2,1]

第二次反转前 k 个元素：

[7,6,5]

变成：

[5,6,7]

第三次反转后 n - k 个元素：

[4,3,2,1]

变成：

[1,2,3,4]

最终得到：

[5,6,7,1,2,3,4]

这正是右轮转 3 位的结果。

解法三：环状替换

环状替换的思路是：直接把每个元素放到它应该去的位置。

根据公式：

next = (current + k) % n

当前位置 current 的元素应该移动到 next。

但如果直接赋值，会覆盖 next 原来的元素。

所以需要用一个变量 prev 保存当前要移动的值：

int prev = nums[start];

然后每次把 prev 放到目标位置，并把目标位置原来的值交换出来，继续移动：

swap(nums[next], prev);

这样就沿着一个环不断移动。

例如：

nums = [1,2,3,4,5,6,7], k = 3

从下标 0 开始，会经过：

0 -> 3 -> 6 -> 2 -> 5 -> 1 -> 4 -> 0

这一圈刚好覆盖全部元素。

但不是所有情况都只需要一圈。

例如：

n = 4, k = 2

下标移动关系是：

0 -> 2 -> 0

1 -> 3 -> 1

这时一圈只能覆盖一部分元素，所以代码需要从多个起点开始。

变量 count 表示已经移动了多少个元素。

当：

count == n

说明所有元素都已经移动到正确位置，可以停止。

环状替换为什么正确

环状替换按照映射关系移动元素：

i -> (i + k) % n

这正是右轮转的目标下标。

对于每一个被访问到的下标，算法都会把原来应该放到这里的元素放进去。

如果某一圈回到了起点，说明这个环中的所有位置都已经完成移动。

如果还有元素没有移动，count < n，算法会从下一个起点开始处理新的环。

由于每次移动都会让一个元素进入它的目标位置，并且 count 最终达到 n，所以所有元素都会被移动一次，且都会到达正确位置。

因此环状替换算法正确。

正确性证明

我们证明三次反转法可以正确完成右轮转。

设原数组被分为：

A B

其中：

  • A 是前 n - k 个元素
  • B 是后 k 个元素

右轮转 k 位的目标就是：

B A

第一次反转整个数组：

A B -> reverse(B) reverse(A)

第二次反转前 k 个元素：

reverse(B) -> B

第三次反转后 n - k 个元素：

reverse(A) -> A

所以最终结果是：

B A

这正好等于右轮转 k 位后的数组。

因此三次反转法正确。

辅助数组法直接根据下标公式：

temp[(i + k) % n] = nums[i]

放置每一个元素，因此也正确。

环状替换法同样按照这个下标映射移动元素，并通过 count 保证所有元素都被处理，因此也正确。

复杂度分析

解法一

  • 每个元素放入辅助数组一次
  • 时间复杂度：O(n)
  • 额外使用一个长度为 n 的数组
  • 空间复杂度：O(n)

解法二

  • 三次反转总共处理 n + k + (n - k) = 2n 个元素级别的操作
  • 时间复杂度：O(n)
  • 只使用常数个变量
  • 空间复杂度：O(1)

解法三

  • 每个元素恰好被移动一次
  • 时间复杂度：O(n)
  • 只使用常数个变量
  • 空间复杂度：O(1)

解法四

  • 标准库 std::rotate 的时间复杂度是 O(n)
  • 通常可以视为原地操作
  • 空间复杂度：O(1)

总结：

方法 时间复杂度 空间复杂度 是否原地
辅助数组 O(n) O(n) 否
三次反转 O(n) O(1) 是
环状替换 O(n) O(1) 是
标准库 rotate O(n) O(1) 是