考研笔记

板子：删除所有值为 x 的元素（k 计数法）

用 k 记「已经保留下来的元素个数」。扫一遍，不是 x 的就放到 A[k]。一趟扫描完成，原来的相对次序不变。

代码

void delX(int A[], int &n, int x) {
    int k = 0;                              // k：保留下来的元素个数，A[0..k-1] 是结果
    for (int i = 0; i < n; i++)
        if (A[i] != x) A[k++] = A[i];       // 不是 x 就留下；k <= i，不会覆盖还没扫到的元素
    n = k;                                  // 更新长度，所以参数是 int &n
}
 
void delX(SqList &L, int x) {               // 顺序表版本，只是改了名字
    int k = 0;
    for (int i = 0; i < L.length; i++)
        if (L.data[i] != x) L.data[k++] = L.data[i];
    L.length = k;
}

复杂度：时间 ，空间 。

本质：按条件过滤

把 A[i] != x 换成任何「要保留的条件」，就能解一类题：

题目保留条件
删除所有值为 的元素A[i] != x
删除值在 之间的元素（王道 2.2）A[i] < s 或 A[i] > t
删除所有负数A[i] >= 0
有序表去重A[i] != A[k-1]，见 有序表去重与合并

另一种等价写法是用 k 记已删除的个数，每个保留的元素前移 k 位：A[i-k] = A[i]。

易错点

  • 不要找到一个就删一个、再把后面整体前移，那样是 。
  • 最后要更新长度 n = k，所以参数必须写成 int &n。
  • 有序表删除 也可以先二分找到这一段再整体前移，但 k 计数法对有序表、无序表都能用，考场首选。

链接

反向链接