轮转数组 图解题解

这道题真正在问什么

把数组整体向右轮转 k 个位置：尾部的 k 个元素绕到最前面，其余元素整体后移。比如 [1,2,3,4,5,6,7] 右移 3 位得到 [5,6,7,1,2,3,4]。难点不在轮转本身，而在附加要求：原地完成、额外空间 O(1)——「开一个新数组、把每个数放到 (i+k) % n」这条最顺手的路一开始就被堵死了。

为什么开新数组和逐位右移都不行

开新数组按 (i+k) % n 搬运最好写，但要 O(n) 额外空间，不满足原地。另一个直觉是「整体右移一位、重复 k 次」：每移一位要挪动全部 n 个元素，k 次合计 O(nk)，k 接近 n 时退化成平方级。两条路都堵住之后，问题变成：能不能只靠原地交换、让每个元素只动常数次，就落到最终位置？三次反转正是这样一个答案。

三次反转为什么恰好等于轮转

观察轮转后的形态：它就是「尾部 k 个元素作为一块搬到前面，前 n-k 个作为一块跟在后面」——两块内部顺序不变，只是块的位置对调。而反转有个可利用的性质：整体反转一次，两个块的位置就对调了，代价是每块内部也被反了过来。那就再各补一次反转把内部掰正：整体反转后，前 k 个正是原来的尾块（内部倒序）、后 n-k 个正是原来的头块（内部倒序），分别再反转一次，两块内部恢复正序，整个数组恰好就是轮转结果。

拿示例验证一遍：[1,2,3,4,5,6,7] 整体反转得 [7,6,5,4,3,2,1]；反转前 3 个得 [5,6,7,4,3,2,1]；再反转后 4 个得 [5,6,7,1,2,3,4]，正是右移 3 位的答案。

k 取模和区间端点为什么容易错

第一步必须 k %= n：轮转 n 次等于没转，k 大于等于 n 时真正有效的位移只有 k % n，不取模轻则做无用功，重则反转区间越界。第二个易错点是三段区间的端点：整体是 [0, n-1]，前段是 [0, k-1]，后段是 [k, n-1]，分界点差一格结果就整体错位。取模后 k 为 0 时前段区间为空，反转自然什么都不做，结果依旧正确，不需要特判。

复杂度怎么算，还有别的原地做法吗

三次反转合计每个元素至多被交换常数次，时间 O(n)；全程只在原数组上交换，空间 O(1)。另一种 O(1) 空间的做法是环状替换：从某个下标出发，把每个数直接送到 (i+k) % n 的目标位置、沿环走完，环的个数与 gcd(n,k) 有关。它同样是线性时间，但下标推导容易出错，面试和实战里三次反转都是更直观稳妥的首选。

Python

def rotate(nums, k):
    n = len(nums)
    k %= n                      # 先对 n 取模
    def rev(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1; hi -= 1
    rev(0, n - 1)               # ① 整体反转
    rev(0, k - 1)               # ② 反转前 k 个
    rev(k, n - 1)               # ③ 反转后 n-k 个

C++

void rotate(vector<int>& nums, int k){
    int n = nums.size();
    k %= n;                     // 先对 n 取模
    reverse(nums.begin(), nums.end());            // ① 整体
    reverse(nums.begin(), nums.begin() + k);      // ② 前 k
    reverse(nums.begin() + k, nums.end());        // ③ 后 n-k
}

Java

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;                     // 先对 n 取模
    reverse(nums, 0, n - 1);    // ① 整体反转
    reverse(nums, 0, k - 1);    // ② 反转前 k 个
    reverse(nums, k, n - 1);    // ③ 反转后 n-k 个
}
private void reverse(int[] a, int lo, int hi) {
    while (lo < hi) {
        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
        lo++; hi--;
    }
}