分析

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

---

题解

转k个位置，实际结果是数组大小对偏移量造成影响，最后会循环偏移，所以我们只考虑k % nums.size()个位置。

使用额外数组

核心思想

转k个位置，实际就是从后面取连续k个元素，拿到开头，然后拼接原先头部分。我们可以用额外的数组来处理。

代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        if(k == 0) return;
        vector<int> temp(n);
        for(int i = 0; i < n; i++){
            temp[(i + k) % n] = nums[i];
        }
        nums.swap(temp);
    }
};

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

环状替换

核心思想

1. 元素的最终位置

数组向右轮转 k 位，下标为 cur 的元素，最终落脚位置为：

$next = (cur + k) \bmod n$

每个元素都有唯一的目标位置，我们可以直接把元素送到最终位置，不需要整体平移。

2. 为什么叫“环状”？

不断执行 $cur \to (cur+k)\bmod n$，有限个下标一定会出现闭环：

从起点出发，跳若干步后 回到起点，形成一个环。

整个数组会被切分成若干个互不相交的环，每个环独立完成轮转。

举例：$n=4,\ k=2$

• 环1：0 → 2 → 0

• 环2：1 → 3 → 1

两个环互不干扰，各自内部完成元素移位。

3. 为什么不能直接赋值覆盖？

如果直接 nums[next] = nums[cur]，会覆盖掉 nums[next] 的原值，导致该位置元素丢失，无法继续向后移位。

解决方案：临时变量接力

• 用 prev_val 保存当前需要搬运的数值

• 将该值放入目标位置

• 取出目标位置旧值，作为新的待搬运值继续传递

本质：沿着环接力挪数，不丢值、不重复、不漏移。

核心数学推导

1. 基础等式

在一个环中：走 b 步（访问 b 个元素），每步偏移 k，最终回到起点。

总偏移量是数组长度的整数倍：

$bk = an$

• b：单环元素个数

• a：遍历过程绕数组的圈数

2. 最小公倍数约束

第一次回到起点即停止，说明取最小合法解：

$an = \text{lcm}(n,k)$

代入得单环元素数量：

$b = \dfrac{\text{lcm}(n,k)}{k}$

3. gcd 与 lcm 核心恒等式

数论核心公式（必须熟记）：

$\gcd(n,k) \cdot \text{lcm}(n,k) = n\cdot k$

变形：

$\text{lcm}(n,k) = \dfrac{n\cdot k}{\gcd(n,k)}$

4. 最终关键结论

代入化简，得到两个终极结论：

1. 环的总数量 = gcd(n, k)

2. $\dfrac{n}{\gcd(n,k)}$每个环的元素个数 =

5. 实例验证

示例1：$n=4,k=2,\ \gcd=2$

• 环数量：2

• 单环元素数：$4/2=2$

示例2：$n=7,k=3,\ \gcd=1$

• 环数量：1（整个数组一个大环）

• 单环元素数：7

代码

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 cur = start;
            int prev_val = nums[start];
            do{
                int next_idx = (cur + k) % n;
                swap(prev_val, nums[next_idx]);
                cur = next_idx;
                count++;
            }while(cur != start); // 回到起点，本环结束
        }
    }
};

时间复杂度：$O(n)$，每个元素仅被搬运、访问一次 空间复杂度：$O(1)$，纯原地修改，仅使用临时变量

关键细节深度解析

1. 为什么必须 k %= n？

轮转 n 位等于不轮转，消除多余步数，避免下标越界、死循环。

2. 为什么用 do-while 而非 while？

环的起点 cur == start，while 会直接跳过循环；do-while 先执行、后判断，保证每个环至少完成一次移位。

3. 为什么需要 count 计数器？

当 $\gcd(n,k)\neq1$ 时存在多个环，单个环无法处理全部元素。count 保证 恰好处理 n 个元素，全部归位即终止，无需手动计算环的数量。

三次反转

核心思想：右移 k 步等价于三次反转

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

代码

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());
    }
};

手写 reverse，不调用库函数版本

void myReverse(vector<int>& nums, int l, int r){
    while(l < r){
        swap(nums[l], nums[r]);
        l++; r--;
    }
}
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        myReverse(nums, 0, n-1);
        myReverse(nums, 0, k-1);
        myReverse(nums, k, n-1);
    }
};

时间复杂度：$O(n)$，每个元素最多被反转 2 次 空间复杂度：$O(1)$，O(1)，原地修改，不开辟数组

三种原地方案对比

方法	时间	额外空间	特点
三次反转	O(n)	O(1)	代码最短，考试首选
环状替代	O(n)	O(1)	理解稍难，多环场景要 count
辅助数组	O(n)	O(n)	逻辑最简单

189. 轮转数组 - 力扣（LeetCode）