从蓝桥杯ALGO-90题解析哈希表与排序算法在众数问题中的应用

1. 项目概述从一道“简单”题看算法竞赛的思维陷阱拿到“ALGO-90 出现次数最多的整数”这个标题很多刚接触蓝桥杯或者算法练习的同学可能会松一口气。这不就是统计一个整数序列里哪个数出现最多吗听起来比动态规划、图论要友好太多了。我刚开始刷题时也是这么想的直到被这道题“教育”了几次。这道题被归在“无序阶段”恰恰点明了它的核心挑战数据是无序输入的你无法依赖任何预先的排序必须在一次遍历或者有限的几次操作内高效、准确地找出那个“众数”。它考察的远不止基础的循环和统计更深入到对数据规模的理解、边界条件的处理以及如何在看似简单的逻辑下写出健壮、高效的代码。这正是一个算法竞赛选手从“能写代码”到“能写出好代码”必须跨越的一道坎。这道题适合所有正在准备蓝桥杯或其他算法竞赛的初学者尤其是那些已经掌握了数组、循环、条件判断等基本语法但面对具体问题时容易忽略细节、导致丢分的同学。通过深度拆解这道题我们不仅能学会如何解决“统计众数”问题更能建立起应对竞赛题目的系统性思维如何审题、如何设计算法、如何测试、如何规避陷阱。接下来我们就抛开“简单”的偏见把它当作一个完整的实战项目从里到外剖析一遍。2. 核心需求与解题思路拆解2.1 问题本质与输入输出规格还原首先我们必须从零开始还原题目。虽然我们只有标题但根据蓝桥杯 ALGO 系列题目的普遍风格和“出现次数最多的整数”这个明确描述可以推断出题目的典型样貌核心需求给定一个包含 N 个整数的序列找出其中出现次数最多的那个整数。如果出现次数最多的整数有多个则输出其中最小的那个。这是一个非常经典且明确的“众数”问题但竞赛题总会在细节上设置关卡。输入格式基于常见情景推断 第一行是一个整数 N表示接下来要输入的整数个数。 第二行是 N 个用空格分隔的整数。 例如6 10 20 30 20 30 30输出格式 一个整数即出现次数最多如果并列则取最小的那个整数。 对于上述输入输出应为30因为它出现了3次多于其他的数。约束条件关键 这是最容易出错的部分。根据经验这类题目的数据规模N可能很大比如 N 最大为 10000, 100000 甚至更大。这意味着我们不能使用时间复杂度为 O(N²) 的双重循环暴力比对算法否则会超时。同时整数的取值范围也需要考虑如果范围很大例如 -10^9 到 10^9直接用数组下标作为计数器的“桶排序”思想可能会因为需要申请超大数组而导致内存超限或根本不可行。因此我们的算法必须兼顾时间效率和空间效率。2.2 算法选型与思路对比面对“无序序列找众数”我们有几种常见的思路。选择哪一种直接决定了代码的效率和能否通过所有测试点。思路一暴力双重循环通常不可取对于序列中的每一个数a[i]遍历整个序列统计a[i]出现的次数。记录出现次数的最大值以及对应的数值。时间复杂度O(N²)。当 N10000 时操作次数将达到 1亿 量级在竞赛的时限通常1秒内几乎必然超时。空间复杂度O(1)仅需几个变量。结论仅适用于题目明确说明 N 非常小如 N 500的情况。对于未知规模的竞赛题首先排除。思路二排序后线性扫描先将整个序列排序例如使用快速排序然后遍历一次有序序列。因为相同的数会排列在一起我们可以在遍历时轻松统计每个连续相同数字段的长度。记录下最长长度对应的数字即可对于并列情况由于排序后相同的数字自然聚集且我们是顺序遍历最先遇到的长段对应的数字就是最小的。时间复杂度O(N log N)主要消耗在排序上。后续的线性扫描是 O(N)。对于 N100000快速排序是完全可以接受的。空间复杂度O(N)需要存储整个数组。如果使用原地排序如 C 的sort则主要是数组本身的空间。优点思路直观易于实现。排序后统计逻辑变得非常简单。缺点修改了原数组如果题目不允许修改则需要拷贝。排序的 O(N log N) 虽然对于大数据尚可但并非理论最优。思路三哈希表映射统计这是解决此类问题最通用、最优雅的方法。遍历一次输入序列使用一个哈希表在 C 中是unordered_map在 Python 中是dict在 Java 中是HashMap来记录每个整数出现的次数。即键Key是整数本身值Value是该整数出现的次数。统计完成后再遍历一次哈希表找出值最大且键最小的那个键。时间复杂度O(N)。插入和查询哈希表的平均时间复杂度是 O(1)因此整体是两次线性遍历。空间复杂度O(M)其中 M 是序列中不同整数的个数。在最坏情况下所有数都不同M N。优点理论时间复杂度最优且无需修改原数据。特别适合整数取值范围很大或存在负数的情况。缺点需要掌握哈希表这一数据结构。在遍历哈希表找最大值时需要注意处理键数值的大小比较。我的选择与理由在竞赛中思路三哈希表是首选。理由如下1) 时间复杂度 O(N) 最优面对大数据更有保障2) 不改变输入数据更通用3) 能自然处理负数和大整数。思路二排序作为备选在明确知道数据范围不大且排序函数高效时也可用。我们接下来的详细实现将以哈希表方法为主线同时也会对比介绍排序方法。3. 核心实现与代码详解3.1 基于哈希表映射的C实现我们首先给出最推荐的 C 实现并逐行分析关键点。#include iostream #include unordered_map #include climits // 用于 INT_MIN using namespace std; int main() { int n; cin n; // 陷阱1注意题目是否说明 n 的取值范围。有时 n 可能为0或负数 // 蓝桥杯常见陷阱如果 n0可能不应该有任何输出或需要特殊处理。 // 但根据常理如果n0序列不存在。这里假设题目保证 n 1。 if (n 0) { // 有时题目会说明 n 的取值范围比如 1 n 1000 // 为安全起见可以加上判断若不符合直接返回。 return 0; } unordered_mapint, int countMap; // 哈希表key是整数value是出现次数 int num; for (int i 0; i n; i) { cin num; countMap[num]; // 关键操作如果num不存在会自动插入{num, 0}然后变为1。 } int maxCount -1; // 当前已知的最大出现次数初始化为一个不可能的值如-1 int result INT_MIN; // 当前已知的、出现次数为maxCount的最小数初始化为最小整数 // 遍历哈希表寻找出现次数最多且数值最小的键 for (auto pair : countMap) { // pair是键值对pair.first是数pair.second是次数 if (pair.second maxCount) { // 如果当前数的出现次数严格大于历史最大次数更新结果 maxCount pair.second; result pair.first; } else if (pair.second maxCount) { // 如果出现次数等于历史最大次数则选择数值更小的那个 if (pair.first result) { result pair.first; // maxCount 不变因为次数相同 } } // 如果 pair.second maxCount则忽略 } cout result endl; return 0; }代码关键点解析与避坑指南输入处理与边界cin n;后直接开始循环读入。这里隐藏了一个巨大陷阱有些题目描述不严谨或者测试数据可能包含n0的情况。如果n0后面的循环不会执行countMap为空。在后续寻找result时maxCount保持为 -1result保持为INT_MIN最终会输出一个奇怪的负数这显然是错误的。更安全的做法是在读入n后立即判断如果n 0直接结束程序或进行特殊处理。这是一个非常常见的失分点。哈希表的使用unordered_mapint, int是 C 标准库中的哈希表实现平均插入和查询时间复杂度为 O(1)。countMap[num]这行代码是精髓如果num在map中不存在operator[]会自动插入一个键值对{num, 0}然后对其值进行操作使其变为1。如果num已存在则直接将其对应的值加1。这比先使用find判断是否存在再插入或更新要简洁高效得多。结果更新逻辑这是处理“次数相同时取最小数”的核心。我们维护两个变量maxCount最大次数和result对应的数。当遇到一个出现次数count大于maxCount的数时毫无疑问它成为新的“冠军”我们更新maxCount和result。当遇到一个出现次数等于maxCount的数时我们需要比较这个数pair.first和当前的result谁更小保留更小的那个作为result。注意maxCount不需要改变。这个逻辑确保了最终result是出现次数最多且数值最小的那个整数。初始化技巧maxCount初始化为 -1result初始化为INT_MINC中定义的最小整数值。这样在第一次进入循环时任何一个数的出现次数至少为1都会大于 -1从而能正确初始化。用INT_MIN初始化result是为了在次数相同时比较pair.first result能正确工作任何有效的整数都大于INT_MIN。3.2 基于排序的C实现对比为了理解不同思路我们也看一下排序法的实现。#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; if (n 0) return 0; vectorint nums(n); for (int i 0; i n; i) { cin nums[i]; } // 关键步骤排序 sort(nums.begin(), nums.end()); int currentNum nums[0]; int currentCount 1; int maxCount 1; int result nums[0]; // 初始化结果为第一个数 // 从第二个数开始遍历 for (int i 1; i n; i) { if (nums[i] currentNum) { // 当前数字与前一个相同计数增加 currentCount; } else { // 遇到新数字结算前一个数字的统计结果 // 注意结算逻辑必须在更新 currentNum 之前 if (currentCount maxCount) { maxCount currentCount; result currentNum; } else if (currentCount maxCount) { // 由于是顺序遍历currentNum 一定比之前记录的同次数 result 大吗 // 不一定例如序列 [2,2,1,1]排序后为[1,1,2,2]。 // 当从1切换到2时currentCount(1的计数)2 maxCount被更新为2result1。 // 当遍历结束2的计数也是2此时 currentCount maxCount但 currentNum(2) result(1)所以不更新。 // 这个逻辑是没问题的因为排序后先被遍历到的同次数数字一定更小。 // 所以这里不需要再判断 currentNum result因为 result 记录的就是最先达到 maxCount 的那个最小的。 // 实际上在 currentCount maxCount 时什么都不用做。 } // 开始统计新的数字 currentNum nums[i]; currentCount 1; } } // 重要循环结束后最后一个数字或连续段还没有参与结算 if (currentCount maxCount) { result currentNum; // 这种情况下 maxCount 也会被更新但题目只要求输出数字 // 更严谨的话应该更新 maxCount currentCount; } else if (currentCount maxCount) { // 同样由于是顺序遍历最后一个数字如果次数与最大次数相同它的值一定不小于 result所以无需操作。 // 例如序列 [3,3,2,2,1]排序后[1,2,2,3,3]。result最终是2。 // 最后一个数字3的次数是2与maxCount相同但32所以不更新。 } cout result endl; return 0; }排序法注意事项尾处理这是排序法最容易出错的地方。for循环的统计逻辑是在“遇到新数字”时结算“前一个数字”。这意味着循环结束后最后一个数字或连续段的统计结果currentCount还没有与maxCount进行比较。必须在循环体外再结算一次否则就会漏掉最后一个数。并列处理在排序法中由于是升序遍历任何出现次数相同的数字先被遍历到的那个一定数值更小。因此当currentCount maxCount时我们不需要更新result因为result里保存的就是最先达到这个最大次数的、更小的那个数。这个逻辑比哈希表法更隐晦需要仔细理解。空间与时间使用了vector存储所有数据并进行了排序。对于纯整数排序sort非常高效。但注意如果题目明确要求“不能改变输入数组”则需要先拷贝一份再排序。3.3 Python语言实现示例Python 的字典dict天然就是哈希表实现起来更为简洁。def main(): import sys data sys.stdin.read().strip().split() if not data: return n int(data[0]) if n 0: return nums list(map(int, data[1:1n])) count_dict {} for num in nums: # 使用 get 方法如果键不存在则返回0然后加1 count_dict[num] count_dict.get(num, 0) 1 max_count -1 result float(-inf) # 初始化为负无穷 for num, cnt in count_dict.items(): if cnt max_count: max_count cnt result num elif cnt max_count and num result: result num print(result) if __name__ __main__: main()Python实现要点输入读取使用sys.stdin.read()一次性读取所有输入再分割效率比多次input()更高尤其适合竞赛环境。字典统计count_dict.get(num, 0)是Pythonic的写法功能等同于C中map[num]的自动初始化逻辑。初始化result float(-inf)用负无穷来初始化确保任何整数都比它大。简洁性整体逻辑与C哈希表版本一致但代码更短更易读。4. 边界条件与极端情况测试算法竞赛中普通的逻辑大家都能写对拉开差距的往往是边界情况和极端数据。下面我们设计一系列测试用例来验证我们代码的健壮性。测试用例描述输入样例预期输出验证目的与常见错误基础功能610 20 30 20 30 3030验证基本统计和最大次数判断。次数并列取最小61 2 2 3 3 422和3都出现2次应输出较小的2。所有数字唯一55 4 3 2 11所有数出现次数均为1根据规则应输出数值最小的1。单个元素14242验证 N1 的情况。包含负数5-1 -2 -1 -3 -1-1验证哈希表对负数的支持。大整数31000000000 1000000000 9999999991000000000验证对较大数值范围的处理。N为0或负数的陷阱0(后续无数据)(无输出或程序正常结束不报错)极易出错如果代码没判断n0可能会访问非法内存或输出初始值。我们的代码应包含if n 0: return。最大规模压力测试100000(重复或随机十万个数)(取决于具体数据)验证算法 O(N) 或 O(N log N) 的时间效率确保不超时。使用哈希表法可以轻松通过。所有数字相同10007 7 7 ... 77验证在大量重复数据下的性能。哈希表只有一个键值对效率极高。我的调试心得在写完代码后不要只用题目给的样例。一定要自己构造上表中的这些边界用例进行测试。特别是“N0”和“所有数字唯一”这两种情况很多初学者会忽略。我建议养成一个习惯在本地编写一个简单的测试脚本批量运行这些用例对比输出。对于C选手可以使用assert语句对于Python选手可以写unittest或简单的if判断。这一步能帮你挽回至少20%的冤枉分。5. 算法扩展与变式思考解决了基础问题我们可以看看它的几种常见变式这能帮助我们深化对这类问题的理解。变式1如果要求输出出现次数而不是数字本身这更简单。在我们的代码中最终维护的maxCount变量就是最大出现次数。只需在输出result的同时或单独输出maxCount即可。变式2如果要求输出所有出现次数最多的数并列全部输出这时就不能只维护一个result了。我们需要一个列表或向量来存储所有“当前最大次数”对应的数。当遇到更大次数时清空列表并加入新数当遇到相等次数时将新数加入列表。最后输出整个列表。注意如果要求按升序输出最后需要对列表排序。变式3数据流中的众数无法一次性读取所有数据这是更实际的场景例如实时统计日志中出现最频繁的IP地址。我们仍然可以使用哈希表在线统计。但问题在于内存可能无法存下所有不同的数如果数据流无限且种类极多。这就引出了“流算法”和“多数投票算法Boyer-Moore Algorithm”。但注意Boyer-Moore算法有一个强假设存在一个出现次数超过一半的元素。它可以在O(N)时间和O(1)空间内找到这个“主要元素”。对于不保证存在过半元素的通用众数问题在内存受限的情况下需要使用“损失精度”的近似算法或“抽样”方法。变式4升级为“出现次数最多的前K个整数”这就是经典的Top K Frequent Elements问题LeetCode 347。解决方案是先用哈希表统计频率。然后使用最小堆优先队列维护一个大小为K的小根堆堆顶是当前K个中最小的频率。遍历哈希表若当前元素的频率大于堆顶频率则弹出堆顶插入当前元素。最后堆中剩下的就是频率最高的K个元素。或者使用“桶排序”思想创建一个列表下标为频率值为具有该频率的数字列表。因为最高频率不会超过N所以桶的数量是N1。这种方法在频率分布相对集中时很高效。通过思考这些变式你会发现基础的“统计-比较”思路是核心而不同的约束条件内存、实时性、输出要求会催生出不同的优化算法和数据结构选择。6. 在蓝桥杯赛场上的实战建议结合这道ALGO-90我想给准备蓝桥杯的同学几点更具体的赛场建议仔细阅读数据规模这是选择算法的根本依据。如果题目写明1 N 10^5那么 O(N²) 的暴力法肯定不行。如果写明1 N 10^3那暴力法也许就能过。一定要先看规模使用更快的输入输出方式在C中当数据量很大时cin/cout默认与 C 标准库的同步会导致速度变慢。可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);来关闭同步大幅提升速度。或者直接使用scanf和printf。在Python中使用sys.stdin.read()比循环input()快得多。测试极端案例就像我们前面做的在编码时就要想到N0, N1所有数相同所有数都不同包含负数等情况。在本地用这些案例测试通过能极大增加一次提交通过的信心。注意变量初始化像maxCount和result的初始化一定要用一个“绝对安全”的值。例如用-1和INT_MIN确保第一次比较能正确更新。写完代码后静态检查提交前花一分钟快速过一遍代码循环边界对吗是i n还是i n所有分支情况都考虑了吗尤其是if-else和循环结束后的处理数组/容器下标会越界吗输出格式完全符合要求吗末尾换行了吗这道“出现次数最多的整数”就像一位沉默的考官它用简单的题干测试着你是否具备严谨的思维、扎实的编码和对细节的掌控力。把它吃透你收获的不仅仅是一道题的分数更是一种应对竞赛乃至实际工程问题的稳健态度。在无序的数据中寻找有序的规律本就是算法的魅力所在。