桶子计数

当数字的取值范围不大时，可以给每个可能的值准备一个“桶”——也就是数组的一格——来数它出现了几次。桶的下标就是数值本身，桶里存的是次数。

int cnt[10] = {0};          // 统计 0~9，共 10 个桶
for (int i = 0; i < n; i++)
    cnt[a[i]]++;            // a[i] 这个值又出现一次

要统计 $0$ 到 $9$，就得开 $10$ 个格子（下标 $0$ 到 $9$）。之后 cnt[3] 就是数字 $3$ 出现的次数。复杂度 $O(n)$，扫一遍就统计完，比排序后再数要快。

关键坑是下标越界：桶的大小必须 $\ge$ 最大可能值 $+1$。如果值可能到 $100$，就要开 cnt[101]；值从 $0$ 开始，格子数正好是“最大值 $+1$”。另一个限制是值域不能太大——若数值能到 $10^9$，开这么大的数组内存装不下，这时桶计数就不适用了，得换别的办法。