三次反转数组旋转

B · 三次反转数组旋转

来源：《编程珠玑》开篇问题 B

题意

把长度为 (n) 的一维向量左旋 (i) 个位置。
例：abcdefgh，(n=8)，(i=3) → defghabc。

• 朴素：开长度为 (n) 的临时数组，(O(n)) 时间、(O(n)) 额外空间
• 目标：时间仍约 (O(n))，额外空间只要几十字节（(O(1))）

通俗解法：临时数组

void rotateEasy(char[] a, int i) {
    int n = a.length;
    i %= n;
    char[] b = new char[n];
    int k = 0;
    for (int j = i; j < n; j++) b[k++] = a[j];
    for (int j = 0; j < i; j++) b[k++] = a[j];
    System.arraycopy(b, 0, a, 0, n);
}

好懂，但不满足「几十字节」约束。

专业解法：三次反转

把数组看成两段 X + Y（X 长 i），目标变成 Y + X。

恒等式：

reverse(reverse(X) + reverse(Y)) = Y + X

等价顺序（结果相同）：

1. 先各自翻，再整翻（书上常见）
2. 先整翻，再各自翻（「一页纸先翻面再翻两截」）

口诀：每段被反转两次 → 段内顺序恢复；整体反转一次 → 两段换边。

原理图

新标签打开流程图

交互演示

新标签打开演示

可改数组与 i，切换两种翻法顺序，逐步 / 自动播放。

Java 伪代码

void rotate(char[] a, int i) {
    int n = a.length;
    i %= n;
    reverse(a, 0, i - 1);   // 翻 X
    reverse(a, i, n - 1);   // 翻 Y
    reverse(a, 0, n - 1);   // 整翻
}
 
void reverse(char[] a, int l, int r) {
    while (l < r) {
        char t = a[l];
        a[l] = a[r];
        a[r] = t;
        l++;
        r--;
    }
}

另有「手摇法 / 环状置换」也是 (O(n)) / (O(1))，更绕，面试更常考三次反转。

系列

• 编程珠玑索引