2010·42 数组循环左移：从辅助数组到三次逆置

本文属于「从暴力解到最优解」专题。这道题的题面把「时间和空间两方面都尽可能高效」写在了一起——两个约束同时收紧，暴力解不管走哪条路，总有一头卡住。

题目

设将 n（n > 1）个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 p（0 < p < n）个位置，即将 R 中的数据由 (x₀, x₁, ..., xₙ₋₁) 变换为 (xₚ, xₚ₊₁, ..., xₙ₋₁, x₀, x₁, ..., xₚ₋₁)。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

题面写了「时间和空间两方面都尽可能高效」——按总纲的分类，暴力解和最优解之间存在真实分差，而且这道题特殊在两个维度同时设卡。总分 10 分。

第一步：把暴力解写对

循环左移 p 位，直观看就是「前 p 个搬到末尾，后 n−p 个整体前移」。麻烦在于原地搬会踩数据：x₀ 要去的位置 n−p 上还住着别人。考场上最自然的补救：先把前 p 个抄出来存好，腾出地方让后面的整体前移，最后再把存的接回尾部。

#include <stdlib.h>

void leftShift(int R[], int n, int p) {
    if (p <= 0 || p >= n) return;                // 边界保护：p 越界则不变
    int *tmp = (int *)malloc(p * sizeof(int));   // 暂存前 p 个，防止被踩
    if (tmp == NULL) return;                     // 分配失败保护

    for (int i = 0; i < p; i++)                  // ① 抄出前 p 个
        tmp[i] = R[i];
    for (int i = p; i < n; i++)                  // ② 后 n-p 个整体前移 p 位
        R[i - p] = R[i];
    for (int i = 0; i < p; i++)                  // ③ 暂存段接回尾部
        R[n - p + i] = tmp[i];

    free(tmp);
}

拿 n=5、p=2、R = [1, 2, 3, 4, 5] 走一遍：抄出 tmp = [1, 2]；前移后 R 前三位变成 [3, 4, 5]；接回得 [3, 4, 5, 1, 2] ✓。注意第 ② 步必须从左往右挪——目标位置 i−p 永远在已读位置 i 的左边，不会踩到还没读的数据。

复杂度：三段循环合计 p + (n−p) + p = n + p 次赋值，时间 $O(n)$；辅助数组 tmp 占 p 个 int，空间 $O(p)$。

时间已经线性了，卡在空间上。

它值多少分

按正确性/最优性两个维度（详见总纲）：

• 正确性：设计思想说得清（暂存—前移—接回三步）、代码逻辑自洽、复杂度分析 $O(n)$ 时间 $O(p)$ 空间与实现一致——正确性维度的主体分拿得到。题库解析明确说：这种解法对，只是空间不达标。
• 最优性：题面「两方面都尽可能高效」的期望是 $O(n)$ 时间 + $O(1)$ 空间。时间达标，$O(p)$ 的辅助数组让空间那一档拿不到。

还有另一条暴力路线：整体左移 1 位、重复 p 轮——只用一个临时变量暂存 x₀，空间 $O(1)$ 达标，但每轮挪 n 次、共 p 轮，时间退化到 $O(np)$，时间那一档丢掉。两条暴力路线各卡一头，殊途同归：正确性大头在手，最优性上总有一档拿不到。

对这道 10 分的题来说，暴力解保底已经不差——但这道题的最优解只靠一个 reverse 函数，是历年真题里性价比最高的升级之一。

暴力解的浪费在哪

用总纲的三个问题审一遍：

**有没有重复扫描？**辅助数组版没有——每个元素只被搬动一次；倒是逐位挪版有严重的重复搬运（每轮只前进 1 位，同一个元素被挪 p 次）。

**有没有重算已知的东西？**没有。

有没有放着性质不用？——有，这是关键。辅助数组花 $O(p)$ 空间买的东西只有一样：「别把前 p 个踩掉」。但循环左移是一个置换——每个元素的去处从一开始就完全确定（下标 i 的元素去 (i−p+n) mod n），没有任何信息需要「等一等再决定」。置换原则上可以原地完成，缺的只是一个把它分解成原地步骤的招。

这个招就是逆置恒等式。把 R 拆成两段 $A=(x_0,\dots ,x_{p-1})$、$B=(x_p,\dots ,x_{n-1})$，目标是把 $AB$ 变成 $BA$。数学事实：两段拼接后整体逆置 = 各段先单独逆置再交换顺序，即 $(A^R{B}^R{)}^R=BA$。而逆置本身是标准的原地操作——双指针从两端向中间交换，一个字节的额外数组都不用开。

智慧化改造：三次逆置

顺着恒等式反着拆，就得到三步：

步骤	操作	结果
起始	—	$AB$
1：逆置 R[0..p−1]	$A\to A^R$	$A^{R}B$
2：逆置 R[p..n−1]	$B\to B^R$	$A^R{B}^R$
3：逆置整个 R[0..n−1]	$(A^R{B}^R{)}^R$	$BA$ ✓

拿 n=5、p=2、R = [1, 2, 3, 4, 5] 验证：逆置前两个得 [2, 1, 3, 4, 5]；逆置后三个得 [2, 1, 5, 4, 3]；整体逆置得 [3, 4, 5, 1, 2] ✓。

// 原地逆置 R[low..high]
static void reverse(int R[], int low, int high) {
    while (low < high) {
        int t = R[low];
        R[low] = R[high];
        R[high] = t;
        low++;
        high--;
    }
}

void leftShift(int R[], int n, int p) {
    if (p <= 0 || p >= n) return;       // 边界保护：p 越界则不变
    reverse(R, 0,     p - 1);           // 第 1 段逆置
    reverse(R, p,     n - 1);           // 第 2 段逆置
    reverse(R, 0,     n - 1);           // 整体逆置
}

复杂度：三次逆置各扫自己的段，元素访问数 = p + (n−p) + n = 2n，时间 $O(n)$；只用 t、low、high 三个标量，空间 $O(1)$。两个约束同时达标，这就是标准答案。

从暴力解升级过来，四个细节决定这 10 分能拿多满：

• 三次的顺序是硬约束：必须先两段、后整体。先整体再两段得到的是 $BA$ 的段内又各自逆置的错误形态，顺序错或漏一次都得不到目标序列，按算法错处理。
• 段边界严格对齐：第 1 段是 [0, p−1] 而非 [0, p]，第 2 段是 [p, n−1] 而非 [p+1, n−1]。off-by-one 直接改变分段位置，同样按算法错。
• reverse 的终止条件是 low < high：两指针重合或交错即停。写成 low <= high 在偶数长度段会多做一次自交换，不影响正确性但属于白费操作。
• (1) 问必须解释「为什么三次逆置等于循环左移」：给 $(A^R{B}^R{)}^R=BA$ 的推导，或像上面那样举具体例子验证。只报操作步骤不给依据，设计思想那一问要扣分。

两版对照跑一遍

同一组输入 [1, 2, 3, 4, 5, 6, 7]、p = 3（目标 [4, 5, 6, 7, 1, 2, 3]），先看辅助数组版——注意 tmp 这个新容器的出现，它就是 $O(p)$ 空间的实体：

加载可视化中...

再看三次逆置版——全程只在原数组内交换，没有任何新容器出现：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

• 环式置换（GCD 分组）：沿「i → (i−p+n) mod n」的置换环逐个搬运，按 gcd(n, p) 个环分组，同样 $O(n)$ 时间 + $O(1)$ 空间——判分上与三次逆置等价，都是公认的最优解。但它要处理环的分组与起点，代码明显更绕，考场上三次逆置是更稳的选择。
• 右移是免费赠品：循环右移 p 位等价于左移 n−p 位，三次逆置法直接套用。同一思想还能解「字符串原地反转单词顺序」这类题——reverse 这个函数值得练成肌肉记忆。
• 两条暴力路线的定位：辅助数组版时间达标空间不达标，逐位挪版反过来。它们都是合格的保底解，也都是理解三次逆置价值的参照物。

下一步

• 在 OJ 上把两版代码都提交跑一遍：ds-2010-42 数组循环左移
• 回到题库看这道题的完整解析与错因：真题库 · 数据结构