考研笔记

板子：有序表去重与合并（双指针）

有序是双指针的前提：两个指针都只往前走，不回头，所以一趟 就能扫完。

代码

void dedup(int A[], int &n) {                   // 有序表去重
    if (n == 0) return;                         // 空表要特判，否则下面 k = 1 就错了
    int k = 1;                                  // A[0] 一定保留；A[0..k-1] 是去重后的结果
    for (int i = 1; i < n; i++)
        if (A[i] != A[k - 1]) A[k++] = A[i];    // 和已保留的最后一个比较，不同才收下
    n = k;
}
 
int mergeSorted(int A[], int n, int B[], int m, int C[]) {   // 两个升序表合并到 C，返回长度
    int i = 0, j = 0, k = 0;
    while (i < n && j < m)                      // 两边都还有元素才需要比较
        C[k++] = A[i] <= B[j] ? A[i++] : B[j++];    // <=：相等时先取 A，合并是稳定的
    while (i < n) C[k++] = A[i++];              // 剩下的直接接到后面（两句只会执行一句）
    while (j < m) C[k++] = B[j++];
    return k;
}
 
int intersect(int A[], int n, int B[], int m, int C[]) {     // 两个升序表求交集，返回长度
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (A[i] < B[j]) i++;                   // 小的一方往前走
        else if (A[i] > B[j]) j++;
        else { C[k++] = A[i]; i++; j++; }       // 相等才收下
    }
    return k;
}

复杂度：去重 ；合并、交集 。去重和交集的额外空间是 ，合并需要一个长度为 的数组 C。

同一个骨架还能做

  • 差集 ：交集代码里，A[i] < B[j] 时把 A[i] 收下。
  • 归并排序的 Merge、两个有序链表合并：和 mergeSorted 是同一段代码。
  • 2011 两序列中位数的保底解：按合并的顺序数到第 个，不需要存下来。见 两个等长升序序列的中位数。

易错点

  • 无序表不能这样去重：要么先排序，要么值域小的时候用辅助数组标记（见 辅助数组计数与标记）。
  • 合并时写 <=，相等时先取 A 的元素，这样合并是稳定的。
  • 主循环结束后，两个 while 收尾都要写，不知道哪边先用完。
  • 如果 A 后面还有 个空位，可以从后往前填，直接合并到 A 里，不用 C。

链接

反向链接