统计次数

想知道每个数各出现几次，最快的办法是桶计数：准备一排“计数盒子”cnt，见到数字几，就往第几个盒子里放一颗石子（加一）。

int cnt[10] = {0};          // 统计 0~9，10 个计数盒，先清零
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;               // 见到 x 就在第 x 个盒子加一
}

统计完，cnt[3] 就是数字 3 出现的次数。要找“出现最多的数字”，再扫一遍计数盒，用打擂台挑出 cnt 最大的下标即可：

int best = 0;
for (int d = 1; d < 10; d++)
    if (cnt[d] > cnt[best]) best = d;   // best 就是出现最多的数字

整个过程读入 $O(n)$、找最多 $O(10)$，非常快，是“用空间换时间”的典型——不用两两比较，直接用下标定位。

用桶计数有两个前提和坑：

• 数值范围要已知且不大，因为要按最大可能值开数组。统计 09 开 cnt[10]，统计成绩 0100 开 cnt[101]。
• 计数盒一定要先清零（= {0} 或全局数组自动为 0），否则里面是垃圾值。
• 数字可能是负数或很大时，桶会开不下或下标为负，那就得换用其他计数方式（如映射）。