[考研算法] 001-循环左移

所有的考研题目，为了考试的统一性和易学性，均采用C语言来编写，版本为C17，使用其他版本也可以，仅仅停留在算法层面，各大版本几乎区别不大

1. 题目

2021年真题

设将 $n(n>1)$ 个整数存放到一维数组 $R$ 中。设计一个在时间和空间两方面都尽可能高效的算法。将 $R$ 中保存的序列循环左移 $p(0<p<n)$ 个位置，即将 $R$ 中的数据由 $(X_0,X_1,...,X_{n-1})$ 变换为 $(X_p,X_{p+1},...,X_{n-1},X_0,X_1,...,X_{p-1})$ 。

这是一个经典的算法问题。
为了在时间和空间两方面都尽可能高效，最佳的方法是采用 “三次逆置法”（Reverse Algorithm）。
该算法可以在 $\displaystyle O(n)$ 的时间复杂度和 $\displaystyle O(1)$ 的空间复杂度下完成任务。

2. 算法设计思想

我们可以将数组 $R$ 视为由两个部分组成的：

前部 $A$ ： $\displaystyle (X_0, X_1, ..., X_{p-1})$
后部 $B$ ： $\displaystyle (X_p, X_{p+1}, ..., X_{n-1})$

原始数组为 $AB$ ，我们需要将其转换为 $BA$ 。
利用向量逆置的性质 $\displaystyle (A^T B^T)^T = BA$ ，我们可以通过以下三个步骤实现：

逆置前部：将数组的前 $\displaystyle p$ 个元素 $\displaystyle (X_0, ..., X_{p-1})$ 原地逆置。
逆置后部：将数组的剩余 $\displaystyle n-p$ 个元素 $\displaystyle (X_p, ..., X_{n-1})$ 原地逆置。
整体逆置：将整个数组 $\displaystyle (X_0, ..., X_{n-1})$ 原地逆置。

经过这三步，数组中的数据就变成了 $\displaystyle (X_p, ..., X_{n-1}, X_0, ..., X_{p-1})$ ，即完成了循环左移。

这里我们涉及一些线性代数的知识，数一二三都要考的

3. C语言代码实现

#include <stdio.h>

// 辅助函数：将数组 R 中从下标 from 到 to 的元素逆置
void Reverse(int R[], int from, int to) {
    int i, temp;
    // 使用双指针，i指向头，to指向尾，向中间靠拢并交换
    for (i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

// 主函数：将数组 R 循环左移 p 个位置
void CycleLeftMove(int R[], int n, int p) {
    // 如果 p 非法或无需移动，直接返回
    if (p <= 0 || p >= n) return;

    // 1. 逆置前 p 个元素 [0, p-1]
    Reverse(R, 0, p - 1);
  
    // 2. 逆置剩余 n-p 个元素 [p, n-1]
    Reverse(R, p, n - 1);
  
    // 3. 逆置整个数组 [0, n-1]
    Reverse(R, 0, n - 1);
}

// 测试代码
int main() {
    int R[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = 10;
    int p = 3; // 循环左移3位

    CycleLeftMove(R, n, p);

    printf("Result: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", R[i]);
    }
    // 预期输出: 3 4 5 6 7 8 9 0 1 2
    return 0;
}

4. 复杂度分析

时间复杂度：
该算法主要由三次逆置操作组成。
- 第一次逆置涉及 $\displaystyle p$ 个元素，操作次数约为 $\displaystyle p/2$ 。
- 第二次逆置涉及 $\displaystyle n-p$ 个元素，操作次数约为 $\displaystyle (n-p)/2$ 。
- 第三次逆置涉及 $\displaystyle n$ 个元素，操作次数约为 $\displaystyle n/2$ 。
- 总的操作次数为 $\displaystyle 2n$ 次扫描。
  因此，时间复杂度为 $\displaystyle O(n)$ 。
空间复杂度：
算法是在原数组上进行操作（In-place），只需要用到有限的几个辅助变量（如 i, temp, from, to）来进行交换和循环控制，不需要额外的数组空间。
因此，空间复杂度为 $\displaystyle O(1)$ 。

5. 示例推演

假设 $\displaystyle R = (0, 1, 2, 3, 4)$ ， $\displaystyle n=5$ ， $\displaystyle p=2$ 。目标结果为 $\displaystyle (2, 3, 4, 0, 1)$ 。

逆置前 $\displaystyle p$ 个 ( $\displaystyle 0$ 到 $\displaystyle 1$ )：
$\displaystyle (1, 0, 2, 3, 4)$
逆置后 $\displaystyle n-p$ 个 ( $\displaystyle 2$ 到 $\displaystyle 4$ )：
$\displaystyle (1, 0, 4, 3, 2)$
整体逆置 ( $\displaystyle 0$ 到 $\displaystyle 4$ )：
$\displaystyle (2, 3, 4, 0, 1)$