考研笔记

板子：辅助数组计数与标记（空间换时间）

值域已知而且不大时，开一个数组 B，把「值」当成「下标」：B[v] = 1 表示 v 出现过，B[v]++ 统计出现次数。每次「查一个值有没有出现过」就从 变成了 。

代码（2018：未出现的最小正整数）

int findMissMin(int A[], int n) {
    int *B = (int *)calloc(n + 2, sizeof(int));   // B[v] = 1 表示 v 出现过，calloc 自动清零
                                                  // 下面会读到 B[n+1]，所以开 n+2 个
    for (int i = 0; i < n; i++)
        if (A[i] >= 1 && A[i] <= n) B[A[i]] = 1;  // 答案只可能是 1..n+1，<= 0 或 > n 的值不用管，也不会越界
    int v = 1;
    while (B[v]) v++;                             // B[n+1] 一定是 0，循环一定会停
    free(B);
    return v;
}

复杂度：时间 ，空间 。

关键一步： 个数最多占满 ，所以答案一定在 里，辅助数组开 就够了。

例：{-5, 3, 2, 3} → 1；{1, 2, 3} → 4。

通用写法

// 速记
int *B = (int *)calloc(range, sizeof(int));   // 值域是 [0, range)
B[v] = 1;                                     // 标记：v 出现过（查重、找缺失）
B[v]++;                                       // 计数：v 出现了几次（找众数、主元素）
free(B);

值可能是负数时，下标加一个偏移量：B[v + OFFSET]。

用在哪

题目辅助数组存什么
2018 未出现的最小正整数标记 是否出现
2013 主元素（备选解）计数，题目保证
2015 链表按绝对值去重标记每个绝对值是否出现过
无序表去重标记
计数排序先计数，再按下标从小到大输出

易错点

  • 先想清楚哪些值有用。2018 年这题的关键就是想到答案在 里。
  • 数组长度和 有关时要用 malloc 或 calloc，不要写 int B[n]（C++ 标准不支持变长数组）。
  • malloc 申请的内存要自己 memset 清零，calloc 自带清零。
  • 答复杂度时，空间是 ，不要顺手写成 。

链接

反向链接