C++数据核心B4157：频次统计与计数数组入门解析

1. 题目背景与本质解读1.1 “数据核心”这个标题到底在考什么打卡记录刷到第 2812 题编号 B4157选了这道名字很唬人的“数据核心”。先说结论这道题其实没有它名字听起来那么复杂它的本质可以浓缩成四个字——频次统计。题目的大致设定是给你一串整数让你找出这串数据里出现次数最多的那个数然后输出它本身以及它出现的次数。如果出现次数最多的数不止一个那就选数值最小那个。这在小学生组 C 竞赛里是很常见的考法但它同时也是一个很典型的“筛选题”。为什么这么说因为题面里的每一个限制条件都不是无端加进来的。并列时取最小、数据范围负到正、输入长度上限这三个点只要你漏掉任意一个代码要么跑错要么直接越界崩溃。很多刚上手信奥的同学对题目的态度是“看懂样例就开写”。这种做法在简单题上还能侥幸过关但到了这种带边界条件的统计题往往就是栽跟头的地方。信奥题给的是规则不是故事你需要做的第一件事永远是拆解规则把自然语言翻译成精确的逻辑表达式。“数据核心”去掉修辞外壳后只剩下三件事统计频率、寻找最大、处理并列。1.2 这道题在刷题路线里的位置我说它是入门题但“入门”不代表“不值得做”。恰恰相反这类题目是整个信奥知识体系的承重墙。你后面学排序、学二分、学哈希、学树状数组底层逻辑里都绕不开“把数据组织起来然后快速查询”这个动作。而这道题最朴素的版本就是让你用最直接的方式完成“组织”和“查询”这两个步骤。另外这类题目非常适合放进打卡刷题列表里。因为它的代码量不长几分钟就能完成一次完整的读题、编码、测试、提交闭环很适合培养竞赛手感。但我的建议是不要只满足于一遍过。你至少应该把三种不同的实现思路都写一遍感受一下它们在代码结构、运行速度、空间占用上的差异。这个习惯一旦养成比你多刷三百道重复题目有用得多。2. 解题前的关键抉择用哪条路线2.1 先吃透数据范围再谈算法信息学竞赛里有句经常被提到的话算法选得好不好不由你的喜好决定由数据范围决定。拿到题目第一个动作不是打开编译器而是拿出笔把输入规模、数值范围、时间限制这三个数字圈出来。B4157 这道题里常规设定是 N 不超过 10000单个数值落在 -100000 到 100000 之间。这个范围给了我们一个很强的信号值域是连续且已知的总共只有 200001 种可能。这意味着什么意味着我们可以用一个长度为 200001 的数组把每个输入值直接映射到数组下标下标位置记录它出现的次数。整个过程不需要排序也不需要复杂的查找结构。如果数值范围扩大到 10⁹数组方案就废了因为谁也不可能开一个十亿长度的数组。如果值域不确定那就要考虑哈希表。这些判断不能靠感觉必须靠对数据范围的敏感度。这也是刷题量积累的核心收益之一——你见得多了一眼就能定方案。2.2 三种常见解法的对比我把这道题的常见解法整理了一下你对照着看会很清楚方案时间复杂度空间复杂度适用场景代码难度暴力双层循环O(N²)O(1)N 极小几百低计数数组O(N M)O(M)M 为值域大小值域连续且可控低哈希表unordered_map平均 O(N)O(K)K 为不同值的个数值域大或不确定中暴力双层循环的思路是最朴素的外层遍历每一个数内层再遍历一遍整个数组数一数它出现了多少次最后维护一个最大值。这个方案的时间复杂度是 O(N²)当 N 达到 10000 时最坏情况要做一亿次比较。虽然数据量小的时候确实能跑但在竞赛场景里这属于把简单问题做复杂而且完全没体现出“数据组织”的思想。计数数组是我最推荐初学者掌握的方案。它利用数组随机访问 O(1) 的特性把统计过程压缩成一次遍历。你来一个数我就往对应的格子里加一最后沿着数组扫一遍边扫边记录最大值和对应的值。只要偏移量处理正确几乎不可能写错。哈希表在这里属于“能过但没必要”。它的优势是对值域范围没要求可以自动只存储出现过的数字。但它有额外的哈希计算开销在 200001 个连续整数面前它的常数比数组下标访问大得多。而且无序哈希表的遍历顺序不固定你在处理“并列取最小”的时候还得额外记录最小值代码反而更绕。2.3 负数值与偏移量的处理数组下标不能是负数这是这道题给新手的第一道坎。数值范围是 -100000 到 100000所以我们需要一个偏移量 OFFSET把负数抬到非负区间。这本质上是一次坐标平移把所有数字整体加上 100000映射到 [0, 200000] 的空间里。两个转换公式必须刻进脑子里写入计数时cnt[x OFFSET]还原数值时value index - OFFSET我见过不少同学统计部分写对了输出时忘了把下标减回去结果答案全带偏移量。这种错误在你做完十道题之后回想起来会觉得特别幼稚但在考场当下紧张和手忙脚乱叠加就是会让你漏掉这一个小细节。解决方案很简单把 OFFSET 定义成全局常量并且在写还原公式的时候顺手写一行注释长时间盯着代码的人是不会犯这种低级失误的。3. 完整 C 实现与逐步拆解3.1 全局数组和读入优化先给出一个可以直接提交的完整版本。我尽量把每一处关键的代码都配上说明让初学者能照着理解而不是照着抄。#include iostream using namespace std; const int OFFSET 100000; const int MAX_RANGE 200001; // 全局变量默认全部初始化为 0 // 下标范围 0 ~ 200000对应数值 -100000 ~ 100000 int cnt[MAX_RANGE]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; for (int i 0; i N; i) { int x; cin x; cnt[x OFFSET]; } int bestValue -OFFSET; int bestCount -1; for (int i 0; i MAX_RANGE; i) { if (cnt[i] bestCount) { bestCount cnt[i]; bestValue i - OFFSET; } } cout bestValue bestCount \n; return 0; }这段代码的核心模块只有三个读入、统计、扫描输出。读入和统计合并在一趟循环里完成因为计数数组本身就是一个可以在线更新的数据结构。你来一个数我立刻登记不需要把原始数据先存起来。这一点跟暴力法有本质区别——暴力法必须把原始数组留着反复扫描而计数数组只需要保留汇总信息就够了。3.2 扫描时“严格大于”的巧妙之处很多同学在选最优值时习惯写if (cnt[i] bestCount)。这道题里这个写法就是典型的错误示范。因为题目要求“出现次数并列时取数值较小”而我们扫描数组下标是从小到大进行的。如果你用那么遇到后面更大的数值时即使它的计数跟当前最优值一样大也会覆盖掉前面的记录最终输出的就是较大的那个值。用就可以完美规避这个问题只有当某个数值的出现次数严格大于当前最优记录时才更新最优值。这样扫描结束时存下来的永远是下标最小、同时计数最大的那个数值。一句话总结帮你实现了“并列优先取小”不需要再额外写任何判断分支。这个写法是我强烈推荐掌握的。因为它不是针对这道题的奇技淫巧而是“顺序扫描时要保持首个最大值”这一通用技巧。后面你写滑动窗口、写单调栈、写各种贪心维护最优值时都会反复用到这种“非严格不更新”的思想。3.3 样例推导过程拿一组简单数据验证一下逻辑。假设输入6 3 5 -1 3 5 4统计表如下数值出现次数-11324152出现两次的数字有 3 和 5按照题目规则取较小的 3所以正确答案是3 2。再看代码的执行过程扫描到 3 对应的位置时cnt 值为 2更新最优为 3扫描到 5 对应的位置时cnt 值也是 2但因为不满足cnt[i] bestCount所以保持不变。输出3 2与预期完全一致。这种手动推导非常值得做。初学者往往依赖在线评测系统告诉你答案对错但你有必要先学会自己判断对错。拿出一张纸把样例输入跑一遍代码的逻辑流程画出每一个变量的变化过程这比任何调试工具都更能帮你建立程序思维。4. 刷题过程中的高频踩坑点4.1 数组开小了RE 还是 WA第一种经典错误数组长度只开到 100001忽略负数部分。当你输入 -100000 时x 100000等于 0看起来好像没事可当你输入 100000 时下标 200000 越过数组边界轻则访问到未知内存重则段错误崩溃。这就是运行错误 RE 的常见来源。还有一种反向错误数组长度开对了但偏移量写成了负数。比如cnt[x - OFFSET]正数会跑到数组前部负数会变成巨大的下标程序跑起来就爆炸。这类错误的排查思路其实很简单在代码开头加一个断言或者针对 -100000、100000 这两个边界值单独测试能跑通再提交。4.2 全局数组和局部数组的选择很多人习惯把所有变量都写在 main 函数里这在小规模题目里没问题但在这道题上我建议把大数组放到全局区。原因有两点第一全局数组由系统自动初始化为 0你省去手动 memset 的步骤第二局部变量存放在栈区栈空间通常在几 MB 量级一旦数组开大比如超过几百万个整数直接栈溢出崩溃。有些同学喜欢用vectorint cnt(MAX_RANGE)放在 main 里这也是一种方案。vector 的对象在堆上分配不会爆栈而且有自动初始化代码也很干净。我只是觉得对于这种固定范围的计数场景直接开一个全局原生数组是最干脆的既不用 include vector 头文件又能体现 C 面向系统底层的直接性。4.3 输出缓冲endl 和 \n 的区别初学者最容易忽略的输出细节是\n和endl的差异。两者从显示效果看都是换行但 C 底层逻辑完全不同。endl的本质是输出换行符之后再冲刷一次输出缓冲区而\n只是纯换行不冲刷缓冲区。在大量输出场景里频繁刷缓冲会大幅拖慢程序运行速度。虽然这道题只输出一行用哪个都无伤大雅但我强烈建议你从一开始就统一用\n。这个习惯在后续题目里会帮你省下很多时间。同样的道理读入方面ios::sync_with_stdio(false)和cin.tie(nullptr)这两行我每一道题都会写已经变成肌肉记忆了。4.4 常见错误速查表症状可能原因排查方法程序崩溃RE数组长度不足检查是否覆盖 -100000 到 100000程序崩溃RE偏移量符号写反用边界值测试答案错误WA并列条件用了 改成严格大于答案错误WA输出时没还原下标确认使用i - OFFSET答案错误WA初始化 bestCount 为 0改成 -1避免计数恰好为 0 时判断出错最后这一条容易被忽略如果把 bestCount 初始化为 0而某个数字出现次数恰为 0那么判断条件cnt[i] 0恒不成立程序依然能工作但如果出现次数本身可能为 0 且你希望保留“至少出现一次”这个前提用 -1 作为初始值在逻辑上更严谨。在这道题里每个输入值至少出现一次所以 0 和 -1 都不会出问题但统一写成 -1 是更专业、更稳妥的习惯。5. 从这道题延伸到更广的统计场景5.1 数据规模变大时的升级路径B4157 只是一个小切口。如果同样的题面把 N 改成 10⁶把数值范围改成 -10⁹ 到 10⁹那计数数组就直接失效了因为没人能开一个长度为 2×10⁹ 的数组。此时标准的替代方案是std::unordered_map只在出现过的数值上开桶统计。#include iostream #include unordered_map using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; unordered_mapint, int freq; for (int i 0; i N; i) { int x; cin x; freq[x]; } int bestValue, bestCount -1; for (auto p : freq) { if (p.second bestCount) { bestCount p.second; bestValue p.first; } } cout bestValue bestCount \n; return 0; }但是注意了这个版本有一个隐患它在处理“并列取最小”时需要额外的逻辑因为哈希表的遍历顺序是无序的不能依赖遍历顺序来保证“取小”。正确做法是在更新条件里加上p.second bestCount p.first bestValue的并列判断。这只是技术细节但很能说明一个道理同样的逻辑搬到不同的数据结构上边界条件的处理方式会完全不同。5.2 频次统计模型在工程里的影子不要觉得“统计出现次数最多”只是竞赛题。你在真实的工程场景里会反复遇到它。电商后台想找销量最高的商品日志分析系统想找最频繁出现的错误码编译器想找哪些变量名出现次数最多这些都是同一个模型的变种。工程里实现它可能是用 Redis 的哈希表配合原子计数也可能是用数据库的 GROUP BY 语句但底层思想跟这道题一模一样把数据映射到计数器上然后查找最大值。竞赛题的价值不在于让考生背住某道题的代码而在于彻底理解这个“映射-计数-查询”的抽象过程。你在这道题里亲手写一遍数组下标映射以后看任何频次统计的方案都能一眼识别出它的本质。5.3 把一道简单题做出复杂效果我在平时的刷题复盘里有个固定的操作每做完一道题不急着标记完成而是做三件事。第一尝试用另一种数据结构重写第二把数据范围改大看当前的代码还能不能过第三故意引入一种经典错误观察程序输出强化对错误症状的记忆。比如这道题我至少会写四个版本计数数组版、unordered_map 版、map 版、暴力版。然后把四个版本放在同一组随机数据上跑记录耗时差异。这个过程大约花二十分钟但对数据结构和复杂度的理解比刷十道模拟题都深刻。打卡刷题的意义从来不是完成数量指标而是通过一个又一个具体题目把模糊的概念变成肌肉记忆。B4157 这道“数据核心”就是这样一个适合反复咀嚼的标本。你把它吃透了后面遇到的统计类题目对你来说都只是换了一层壳。