题目

设将 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) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：三次逆置法——先把 R[0..p-1] 整段逆置一次，再把 R[p..n-1] 整段逆置一次，最后把整个 R[0..n-1] 逆置一次。完成后 R 就是循环左移 p 位的结果。

为什么这三步等价于循环左移？

记原序列为 ，目标 。

把 拆成两段 和 ，目标就是把 变成 。三次逆置：

步骤	操作	结果
起始	—
1：逆置 R[0..p-1]
2：逆置 R[p..n-1]
3：逆置整个 R[0..n-1]		✓

数学事实：两段拼接后整体逆置 = 各段先单独逆置再交换顺序。三次逆置的本质就是把这条恒等式拆成三个 in-place 操作。

举例验证：n=5、p=2、R = [1, 2, 3, 4, 5]，目标 [3, 4, 5, 1, 2]。

步	操作	R 状态
起	—	[1, 2, 3, 4, 5]
1	逆置 R[0..1]	[2, 1, 3, 4, 5]
2	逆置 R[2..4]	[2, 1, 5, 4, 3]
3	逆置 R[0..4]	[3, 4, 5, 1, 2] ✓

(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);           // 整体逆置
}

关键点说明：

• 三次逆置是经典 in-place 招数：避免开辅助数组、避免复杂的"环式置换"——三次双指针扫描搞定。
• 每次 reverse 用 while + 两端向中间靠拢：常数次比较与交换，平均每段 O(段长 / 2)。
• 边界保护：题面说 0 < p < n 已经排除了平凡情况，工程代码里仍然加 if 防御不亏。
• 不要分开存"前 p 个"再拼接：int *tmp = malloc(p * sizeof(int)); memcpy(...) 这种解法对，但空间 O(p) 不是题目要求的"两方面都尽可能高效"。三次逆置 O(1) 空间、O(n) 时间，是公认的最优解。

(3) 复杂度分析

• 时间复杂度 ：三次逆置每次扫描各自的段，总元素访问数 = ，线性。
• 空间复杂度 ：除入参 R 外，只用 t、low、high 三个标量，与 n 无关。

编者注（生僻术语）：本题的三次逆置法又叫「反转法 / 翻转法」，是经典字符串/数组操作技巧。同样的思想可以用来解：(a) 字符串原地反转单词顺序（"hello world" → "world hello"）；(b) 任意循环移位（左移 p 等价于右移 n-p，三次逆置法适用）。考研只考左移，但理解后能举一反三。