考研笔记

板子：区间逆置与循环左移

把数组看成 两段，想得到 ：先两段各自逆置得到 ，再整体逆置，。

代码

void reverse(int A[], int l, int r) {      // 逆置 A[l..r]，闭区间
    while (l < r) {                        // l == r 时只剩中间一个，不用换
        int t = A[l]; A[l++] = A[r]; A[r--] = t;   // 交换两端，再往中间收
    }
}
 
void rotateLeft(int A[], int n, int p) {   // 循环左移 p 位
    p %= n;                                // p >= n 时先取模：左移 n 位等于没动
    reverse(A, 0, p - 1);                  // a = A[0..p-1] 逆置
    reverse(A, p, n - 1);                  // b = A[p..n-1] 逆置
    reverse(A, 0, n - 1);                  // 整体逆置，得到 ba
}

复杂度：时间 ，空间 。

例：1 2 3 4 5 6 7， → 3 2 1 | 7 6 5 4 → 4 5 6 7 1 2 3。

考场答案样例（2010）

题意：一维数组 存了 个整数，把它循环左移 位（），即 变成 ，要求时间和空间两方面都尽可能高效。

（1）设计思想：把数组看成 ， 是前 个元素， 是后 个元素。先逆置 得到 ，再逆置 得到 ，最后整体逆置得到 ，就是左移 位的结果。

（2）算法实现：就是上面的代码。

（3）复杂度：三次逆置分别交换 、、 次，时间 ；只用了常数个临时变量，空间 。

变形

  • 循环右移 位 = 循环左移 位。
  • 数组 A[m+n] 前 个和后 个整体换位置（王道 2.2 综合题）：就是循环左移 位。
  • 逆置整个顺序表：reverse(A, 0, n - 1)。
  • 保底解：用辅助数组先存下前 个，其余元素前移，再把存下的放回末尾。时间 ，空间 ，也是正确解。

易错点

  • reverse 的区间是闭区间 ，第二段从 p 开始，不是从 p + 1 开始。
  • 三次逆置可以换成先整体再两段，但分界点要改成 ：reverse(0, n-1); reverse(0, n-p-1); reverse(n-p, n-1)。两种写法混着用就会错。

链接

反向链接