计数问题全解析：从数组标记到哈希表与离散化

经常刷算法题的人，一定见过这种场景：题库里躺着一道编号为1017的题，题面只有一句话——“求零件个数”，没有配图，没有样例解释，评论区一半人问这题到底啥意思，另一半人在贴答案错误的代码。我当年也绕了不少弯才明白，这类题真正要考察的从来不是“数数”，而是你如何在给定约束下高效完成一次统计任务。零件总数、不同零件种类数、每种零件的数量、满足条件的零件数，本质上全是同一个计数模型。下面我就把它拆开讲，从最笨的暴力写法一路推到哈希表、离散化和区间查询，最后附上我刷这类题总结出来的避坑清单，适合刚学数据结构的新手，也适合准备笔试想快速过一遍计数类题目的同学。

1. 题目到底在问什么：先把“零件个数”翻译成计数模型

1.1 典型的题面长什么样

我在不同题库里见过的“1017 - 求零件个数”，绝大多数可以归纳成下面这个版本：

某工厂生产了一批零件，每个零件上都刻有一个整数编号。相同编号的零件视为同一种类。给定 n 个零件的编号列表，请统计：

1. 这批零件总共有多少种不同的编号；
2. 出现次数最多的编号是什么，以及它出现了多少次。 如果出现次数并列，输出编号最小的那个。

这个题面几乎包含了所有计数题的必备要素：输入规模 n、编号的值域范围、去重需求、频次统计需求，还有一个平局判定规则。你要做的不是“数一遍”，而是选择合适的数据结构，在题目给定的时间和空间限制内把答案算出来。“求零件个数”这几个字只是一个壳，壳里面的核心是“统计任务怎么设计、怎么实现、怎么优化”。

1.2 四个常见变体，别被换皮骗了

同样一个标题，在不同题库里可能对应不同的问法。我把常见的变体整理成了一张表，做题时先对照一下，能少走很多弯路：

这四类题表面问法千差万别，但底层的“计数模型”是一致的：先确定你要统计什么，再确定数据组织方式。很多同学拿到题目直接开始写循环，写完才发现统计口径错了，比如把“不同编号数”统计成了“总零件数”，这种错误在代码里非常难发现。

1.3 动手写代码前先问自己三个问题

第一，n 有多大。如果 n 只有几千，O(n²) 的写法也能过；如果 n 到 10⁵ 甚至 10⁶，就必须考虑 O(n) 或 O(n log n) 的解法。第二，编号范围有多大。范围小，数组标记法是最快的；范围大到 10⁹，数组根本开不下，哈希或离散化才靠谱。第三，是不是多组测试数据。很多题目一口气给很多组输入，代码里如果忘了清空容器，上一组的统计结果会污染下一组，直接导致答案错误。这三个问题想清楚，再动手写，正确率会高一大截。

2. 先写跑得起来的暴力版本：数组标记法和排序扫描法

2.1 值域很小时：数组标记法，最快也最直观

如果题目明确说了编号是非负整数，而且编号最大值不超过 10⁶ 甚至 10⁷，那最直接的做法就是开一个计数数组，下标就是编号。每读到一个编号 x，执行 cnt[x]++，最后统计 cnt 里有多少个位置大于 0，就得到不同种类的数量；顺便扫一遍 cnt，就能找到出现次数最多的编号。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); int maxVal = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; maxVal = max(maxVal, a[i]); } vector<int> cnt(maxVal + 1, 0); for (int x : a) cnt[x]++; int kinds = 0; for (int c : cnt) { if (c > 0) kinds++; } cout << kinds << "\n"; return 0; }

这段代码的时间复杂度是 O(n + maxVal)，在值域小的时候比排序还要快，而且逻辑简单、不容易写错。但它有两个明显的限制：一是编号必须是非负整数，如果出现负数，下标就崩了；二是值域不能太大，否则数组内存吃不消。比如编号范围是 0 到 10⁹，你开一个 vector cnt(10⁹+1) 试试，内存直接爆掉。

如果编号是负数但范围不大，可以用偏移法，把所有编号整体平移，让最小值映射到下标 0。比如编号范围是 [-100000, 100000]，就给每个编号加上 100000 再当数组下标。这招在入门题里很常见，但本质上还是在利用值域小的特性。

2.2 不依赖值域：排序后扫描，笔试保底神技

排序是一个非常重要的去重手段。把编号排好序之后，相同的编号一定相邻。这时候用两个指针 i 和 j，j 从 i 开始往后走，走到第一个不等于 a[i] 的位置，那么区间 [i, j) 的长度就是当前编号的出现次数。统计完这个频次之后，i 跳到 j，继续下一段。

sort(a.begin(), a.end()); int kinds = 0; int maxCnt = 0; int bestNum = INT_MAX; for (int i = 0; i < n; ) { int j = i; while (j < n && a[j] == a[i]) j++; int curCnt = j - i; kinds++; if (curCnt > maxCnt || (curCnt == maxCnt && a[i] < bestNum)) { maxCnt = curCnt; bestNum = a[i]; } i = j; } cout << kinds << "\n"; cout << bestNum << " " << maxCnt << "\n";

这段代码的核心技巧是“按时结算”：只有遇到编号变化时，才把上一段的结果结算出去。很多人在统计连续相同元素个数时习惯用一个 curCnt 变量边遍历边改，其实用区间长度算最不容易出错，因为 while 循环天然把边界处理干净了。排序扫描的时间复杂度是 O(n log n)，主要花在 sort 上，后续扫描是 O(n)，整体表现稳定，而且不关心编号范围，不会出现数组越界或内存爆炸的问题。

2.3 暴力法在真实刷题场景里的价值

不少人觉得暴力法是“笨办法”，不屑于写。我个人的观点恰恰相反：在任何笔试或比赛里，第一时间能写出来的、保证逻辑正确的代码，才最有价值。我见过很多同学一上来就写哈希表，结果处理平局规则时漏了“编号最小”这个条件，调试半天才发现问题出在初始值上。而排序扫描版本逻辑是线性的，只要 sort 之后按区间走，很难写错。

正确的策略是先求对，再求快。把排序扫描版本在本地跑通样例、暴力对拍验证逻辑之后，如果题目数据规模确实很大，再考虑优化成哈希版本。这样即使优化失败，手里也有一份能用的代码兜底。

3. 用哈希表把复杂度压到 O(n)：哈希计数与它的不完美之处

3.1 为什么哈希表适合做计数

哈希表（在 C++ 里是unordered_map，在 Python 里是dict）的核心特点是不管数据值域多大，平均读写都是 O(1)。你可以把编号当成“钥匙”，把出现次数当成“柜子里存放的件数”：来一个新编号，就新开一个柜子；来了一个已经见过的编号，就往对应柜子里加一件。整个过程跟编号的绝对大小完全无关，编号就算到 10¹⁸ 也能轻松处理。

哈希表真正适合的场景是“值域很大但实际出现过的编号数量并不多”。比如编号范围是 0 到 10⁹，但一共只给了 10⁵ 个零件，那么哈希表里的键最多也只有 10⁵ 个，内存消耗小，速度又快。这是数组标记法和排序法之间的一个很好的折中方案。

3.2 C++ 完整实现：用 unordered_map 统计频次

直接看代码：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; unordered_map<int, int> cnt; for (int i = 0; i < n; ++i) { int x; cin >> x; cnt[x]++; } // 不同编号的种类数就是哈希表的大小 int kinds = cnt.size(); // 找出现次数最多、编号最小的 int bestNum = INT_MAX; int maxCnt = 0; for (auto &p : cnt) { int num = p.first; int c = p.second; if (c > maxCnt || (c == maxCnt && num < bestNum)) { maxCnt = c; bestNum = num; } } cout << kinds << "\n"; cout << bestNum << " " << maxCnt << "\n"; return 0; }

这里有两个细节值得注意。第一个是ios::sync_with_stdio(false); cin.tie(nullptr);，当输入量到几十万甚至上百万时，不加上这行，cin 的速度会明显拖后腿，加上之后基本能和 scanf 持平。第二个是查找最大频次时，bestNum初始值必须设成极大值，然后在更新条件里写成“次数更大，或者次数相等但编号更小”，这样平局规则才能正确实现。如果初始值是 0，对于编号全为正数的情况碰巧能用，可一旦出现负编号或者编号恰好是 0 的零件，逻辑就出错了。

3.3 Python 版可以写得很短，但平局规则还得自己处理

Python 的collections.Counter天生就是为这种“统计频次”场景设计的：

import sys from collections import Counter data = list(map(int, sys.stdin.buffer.read().split())) n = data[0] a = data[1:1 + n] cnt = Counter(a) best_num = float('inf') max_cnt = 0 for num, c in cnt.items(): if c > max_cnt or (c == max_cnt and num < best_num): best_num = num max_cnt = c print(len(cnt)) print(best_num, max_cnt)

Counter(a)一行就完成了所有频次统计，len(cnt)直接得到种类数，非常省事。但要注意，Counter.most_common(1)虽然能拿到出现次数最多的键值对，却并不能保证“编号最小”的平局规则，所以稳妥起见还是手动遍历一遍。另外，读入时用sys.stdin.buffer.read().split()一次性读入全部数据，比input()一行行读快得多，在处理大输入量时效果立竿见影。

3.4 哈希表与排序怎么选：实测对比和我的选择

数据量小的时候两者差距肉眼几乎看不出来，哪个顺手用哪个。数据量大、编号分布均匀时，哈希法确实更快，平均 O(n) 的优势会体现出来。但哈希法有个隐藏风险：如果输入数据被刻意构造，让所有编号都发生哈希冲突，unordered_map 的最坏复杂度会退化成 O(n²)。竞赛中这种毒瘤数据不多，但在追求极致稳定性的场景下，我会优先选排序扫描法。

4. 数据规模放大之后：离散化与离线查询

4.1 值域大到数组开不下，离散化来救场

数组标记法的失败场景很典型：编号范围是 [0, 10⁹]，但零件只有 10⁵ 个。你想着开数组，却发现需要 4GB 内存，直接爆掉。哈希法能解决问题，但有些人可能希望保持“数组计数”那种清爽的下标访问方式，这就轮到离散化登场了。

离散化的核心思想是“只关心出现过的编号”。把所有出现过的编号收集起来，排序、去重，得到一个有序数组all。原来的每一个编号 x，通过二分查找在all里找到它的位置 id，然后用这个 id 作为新的“紧凑下标”。这样编号范围再大，也只需要一个大小为“不同编号个数”的数组来计数。

整个过程可以理解为“给每个编号发一张序号牌”：不管编号本身是 1、1000 还是 10⁹，它在all数组中的位置都是 0 到 k-1 之间的整数。接下来所有的计数操作，都在这张序号牌上进行。

4.2 离散化计数的 C++ 实现

vector<int> all = a; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); vector<int> cntDis(all.size(), 0); for (int x : a) { int id = lower_bound(all.begin(), all.end(), x) - all.begin(); cntDis[id]++; } int kinds = all.size();

离散化之后，all就是去重后的编号集合，cntDis[id]就是编号all[id]的出现次数。这套写法的预处理复杂度是 O(n log n)，二分查找每次 O(log n)，整体性能相当稳定。它还有一个很实用的附带好处：因为all本身就是排序好的，所以按all数组的下标顺序遍历，就是按编号从小到大遍历，平局规则的“编号最小”可以很自然地处理。

4.3 从“全部统计”升级到“区间统计”

有些题目问的不是“整体有多少种编号”，而是“编号在 [L, R] 范围内的零件有多少个”。这种区间统计用排序加二分是最容易实现的。先把a排好序，然后求两个位置：第一个大于等于 L 的位置，和第一个大于 R 的位置，两者之差就是落在区间内的零件数。

// a 已经排好序 int countInRange(const vector<int>& a, int L, int R) { auto lo = lower_bound(a.begin(), a.end(), L); auto hi = upper_bound(a.begin(), a.end(), R); return hi - lo; }

lower_bound找的是第一个“不小于 L”的元素，upper_bound找的是第一个“大于 R”的元素，两个迭代器相减得到的就是区间内的元素个数。这一招在数据结构题里非常常见，理解了它，后面学树状数组、线段树做动态区间查询时也能少一些陌生感。

值得多说一句的是，如果题目要求“动态修改零件编号后查询区间个数”，排序加二分就不够用了，得换成树状数组或线段树。但从“求零件个数”这道题本身出发，静态排序加二分已经足够解决绝大多数变体。遇到动态场景时再往复杂数据结构迁移，才是合理的学习路径。

4.4 输入输出的性能陷阱，别让 IO 成为 TLE 元凶

很多新手在数据量增大之后发现程序超时，第一反应是算法不够快，其实问题常常出在输入输出上。C++ 的 cin 默认要和 C 的 stdio 保持同步，所以非常慢。解法是在 main 开头加两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

Python 里如果用input()逐行读，数据量大时也扛不住，推荐一次性读：

import sys data = sys.stdin.buffer.read().split()

读进来的全是字节串，再用 int() 批量转换即可。实测同样一份数据，改成批量读入之后，Python 版本的速度可以提升好几倍。无论是刷题还是笔试，养成“先处理输入性能”的习惯，能省下非常多的调试时间。

5. 这类计数题的考场经验与高频翻车点

5.1 五个最容易踩的坑，我全都踩过

第一坑，重复统计。不少人写完cnt[x]++之后顺手kinds++，结果同一个编号出现三次，种类数就加了三次。正确做法应该是在循环结束后遍历整个容器，统计 cnt 中大于 0 的个数，或者用哈希表时直接取cnt.size()。第二坑，负数编号。数组标记法遇到负数编号直接数组越界，需要在读入时整体平移偏移量，而排序法和哈希法天然不受影响。第三坑，多组测试数据没有清空。很多题目是多组输入，上一组统计完的哈希表或数组没有 clear，下一组就会算出错误答案。第四坑，平局条件没实现。题面写了“次数并列时输出编号最小”，代码里却只判断了c > maxCnt，碰巧数据没有并列情况时还能过，一旦出现并列就全错了。第五坑，值域上限看错。题目说编号在 0 到 10⁹ 之间，有人直接开数组，编译都过不了；还有人说“用 long long 不就完了”，但计数数组的内存问题跟数据类型无关，范围大了该离散化还是得离散化。

5.2 提交之前，对照这张自查清单过一遍

我做计数题养成了一个习惯，提交前花三十秒逐项检查这几个问题。题面有没有明确编号非负？如果没有，数组下标就要考虑偏移或直接换哈希。输入规模是多少，我的算法复杂度能不能扛住？如果是多组测试数据，容器初始化放对位置了吗？并列条件处理了吗？输出格式是不是多了空格或者少了换行？这套清单看起来简单，但大部分答案错误的代码，都是栽在这些细节上的。

5.3 一个让调试体验好很多的代码习惯：封装统计函数

我建议把“读入数据、统计频次、寻找最优解”拆成独立的函数，而不是全部堆在 main 里。这样做的好处是可以用小数据集单独调用统计函数做验证，甚至可以写一个简单的对拍器，把暴力法的答案和优化算法的答案逐组比对。比如这样：

pair<int, pair<int, int>> solve(const vector<int>& a) { unordered_map<int, int> cnt; for (int x : a) cnt[x]++; int best = INT_MAX, maxCnt = 0; for (auto &p : cnt) { if (p.second > maxCnt || (p.second == maxCnt && p.first < best)) { best = p.first; maxCnt = p.second; } } return {cnt.size(), {best, maxCnt}}; }

函数返回一个 pair，分别装着“种类数”和“最优编号、出现次数”。本地测试的时候，我可以对同一个测试数据分别调用暴力版和哈希版，对比返回值，快速发现逻辑差异。这种对拍习惯在刷题初期可能觉得麻烦，但越到后期越能体现价值。毕竟，花半小时找出一个隐藏 bug 的成本，远比用五分钟养成好习惯的成本高得多。

我个人刷这类计数题最大的体会是：它不考察什么惊为天人的奇思妙想，考的是你能不能在限定条件下稳定、不出错地完成一次统计任务。跑通一次哈希版本并不难，难的是换个变体、把数据规模放大之后，你还记得什么时候该用数组、什么时候该排序、什么时候该离散化。我的习惯是先写排序扫描版本保证正确性，再换哈希版本拿速度，最后才考虑区间查询这些扩展。这套节奏陪我应付了很多场笔试，也希望你下次看到“求零件个数”这种短题面时，能少走一点弯路。