拿到这道题的时候我盯着题面笑了半天。一个20分的题题解区里一排人抱着unordered_map在数颜色评论区清一色的“用map也能过”。可我最后提交的代码只有12行一次AC运行时间排在榜单前几。不是因为题目简单而是因为大多数人第一反应踩进了“统计频次”这个思维定式里忽略了题目最关键的一句话这个颜色出现次数超过一半。这道1054 The Dominant Color是某程序能力测试平台上的经典题本质是一个众数问题但考的不是你会不会用哈希表而是你有没有识别出“超过一半”这个强约束。如果你正在准备机试、考研复试或者笔试这道题非常值得停下来多想一层为什么不需要统计每一种颜色出现多少次就能把答案找出来这篇文章就把这道题的题面、三种解法对比、12行AC代码的拆解以及我实际踩过的坑全部摊开讲清楚。1. 题面拆解从图像像素到众数模型1.1 还原题面先把输入输出看清楚题目给的场景是图像处理给你一张M列N行的彩色图像每个像素的颜色是一个24位的整数也就是0到16777215之间的数字要求你在所有像素中找出主导色。什么叫主导色题目英文原文是 dominant color明确定义为“出现次数超过所有像素总数一半”的那个颜色。输入格式是第一行给两个整数M和N分别代表图像的列数和行数。注意这里有点反直觉一般我们习惯说“M行N列”但这道题第一维是列第二维是行。后面跟着N行数据每行有M个整数这就是整张图像的所有像素点。输出就一个数主导色的颜色值。举个例子输入3 3 0 0 255 16777215 255 255 0 0 255这里M3N3意味着图像有3列3行共9个像素。数一下颜色0出现了4次255出现了4次16777215出现了1次。0和255都出现了4次但题目有“超过一半”这个硬性要求4/9并没有超过一半所以这个样例理论上不应该合法。题目自身也说明了输入数据保证存在合法的主导色所以实战中你不需要操心“众数不存在”这种边界。1.2 这道题到底在考什么把一个图像问题剥掉外壳剩下的数学模型非常干净给定一个长度为L的序列找出出现次数超过L/2的元素。这是算法里最经典的“多数元素”问题。多数元素问题有几个众所周知的性质如果存在出现次数超过一半的元素那这个元素是唯一的。因为不可能同时有两个元素都出现超过一半。这个元素不用统计完整个序列就能确定因为它能在“两两抵消”的过程中活下来。它和“排序后取中间位置元素”是等价的因为如果某个元素出现超过一半排序后它必然占据中间位置。很多人在考场上第一反应是“我需要知道每个数字出现的次数”然后就开始建哈希表。这个思路没有错但它不是最优解。用哈希表unordered_map去统计空间复杂度是O(K)其中K是不同颜色的数量。在本题数据规模下能过但如果把数据量放大到千万级甚至上亿级别哈希表的内存开销和重建哈希的耗时就会变成明显的瓶颈。题目给了20分分值不高但它想考察的是你看到“超过一半”这个条件之后能不能跳出“统计”思维想到更简洁的抵消算法。如果你上来到处找哈希表的写法说明你对这个条件的利用还不够充分。1.3 容易被忽视的输入规模和性能红线这道题的数据范围如果我去翻原题M和N都在几百的量级总像素数能达到几十万。这个数据量确实不大unordered_map也能轻松跑完。但真正的考点在线下如果你把同样的逻辑放到一个数据规模放大100倍的场景里你的解法还能不能扛住颜色值范围是24位也就是最多约1600万种可能值。想要开一个int count[16777216]的计数数组内存大约是64MB有些评测环境内存限制只有64MB或128MB一开数组就可能爆内存。而且本题输入数据并不保证颜色值连续用数组下标法也很浪费。所以哈希表看起来是合理的但它在极端场景下不是最优的因为空间占用跟“不同颜色的数量”成正比最坏情况下K很大。相比之下下面要讲的摩尔投票法辅助空间只有两个变量不管图像多少像素、颜色有多少种都用O(1)额外空间解决问题。这才是这道题藏在20分背后的教学意义。2. 三种思路对比哈希表、排序、摩尔投票2.1 哈希表统计最直觉但最重绝大多数人看到“找出现次数最多的颜色”第一反应就是unordered_mapint, int cnt; cnt[x];然后遍历一遍找cnt[x]最大的那个颜色输出。这个方案的时间复杂度平均是O(L)期望空间O(K)。看起来不快不慢但在一个讲究“少即是多”的算法题里它有两笔额外开销哈希表本身的内存开销每个键值对除了存数据和计数器还要存哈希节点指针、哈希桶数组。同样的数据量unordered_map的实际内存比普通数组要大好几倍。哈希计算耗时每次插入和查找都要计算hash(x)这个计算在颜色值是大整数时成本不可忽略。我见过很多人用mapint, int红黑树去写那就是O(L log L)纯理论复杂度就输了一截。在几十万数据的规模下能过但代码量多思路也没有踩在题目的“超过一半”这个关键点上。2.2 排序后取中位思路简单但复杂度更高第二种思路更“暴力”把所有颜色值读进一个vectorint排序然后输出v[L/2]。为什么取中间位置就一定对因为一个元素如果出现次数超过一半在有序序列里它必然覆盖中间位置。这相当于把“众数问题”降维成了“中位数问题”。逻辑上没有任何毛病代码也就十几行。但它的复杂度是O(L log L)而且需要一个能装下所有像素的数组空间O(L)。在本题中数据量小没问题但如果给你一亿个像素点这方案在时间和空间上都会被摩尔投票碾压。排序在这里属于“用大炮打蚊子”不是不能用而是没有利用好题目给的最强条件。2.3 摩尔投票法互相抵消活下来的就是答案第三种方案就是我AC代码里用的摩尔投票法Boyer-Moore Majority Vote Algorithm。它基于一个特别直观的生活逻辑假设有一群人在选代表每个人可以投一票。你支持A我支持B那你的票和我的票互相抵消。代表候选人A每出现一次计数器加一遇到一个不是A的人计数器减一。当计数器归零的时候说明当前这堆人里面A和反对A的人打了个平手谁也压不过谁那这一整段就可以直接丢弃因为“超过一半的元素”在剩余部分里依然会超过一半。形式化的流程是维护一个候选值ans和一个计数器cnt初始cnt 0。遍历每个颜色值x如果cnt 0就把ans设为xcnt 1。否则如果x anscnt。否则cnt--。因为题目保证存在出现次数超过一半的颜色遍历结束时ans就是答案。这个算法的精妙之处在于它完全没有记录任何颜色的具体出现次数。它只做一件事配对抵消。众数出现的次数比所有其他数加起来还多所以其他数全部来跟众数抵消众数也还会有剩余。最后活下来的那个候选就是答案。在普遍情况下算法结束时得到的候选只保证是“可能的众数”如果题目没有保证众数一定存在你还需要再遍历一次确认这个候选的出现次数确实超过一半。但这道题在数据范围说明里已经明确了保证存在主导色所以省掉二次验证这也是代码能压到12行的关键前提。2.4 三种方案横向对比拿一张表把这三种方法放在一起看差距一目了然方案时间复杂度空间复杂度代码量是否利用“超过一半”条件适合场景哈希表计数O(L) 期望O(K)中等否需要统计所有颜色频次的业务场景排序取中位O(L log L)O(L)少是数据量小、追求简单摩尔投票O(L)O(1)极少是大流量数据、流式数据注意表格里的K代表不同颜色的数量。如果颜色种类非常多哈希表空间会跟着膨胀摩尔投票则不管颜色有多少种始终只需要两个变量。这就是它能“又短又快”的根本原因。3. 12行代码逐行拆解与实现技巧3.1 完整代码12行一次AC先把我实际提交的代码贴出来然后逐行讲#includebits/stdc.h using namespace std; int m, n, x, ans, cnt; int main() { scanf(%d%d, m, n); for (int i 0; i m * n; i) { scanf(%d, x); if (cnt 0) ans x; cnt (x ans) ? 1 : -1; } printf(%d, ans); return 0; }打包算一下去掉空行和可以合并的行确实就在12行上下。整段代码没有用vector没有用map没有自己写排序只是把题目给的每个数字“过”了一遍。3.2 逐段讲解输入、抵消、输出第一段是头文件和变量声明。#includebits/stdc.h是竞赛常用的万能头文件把标准库全部包含进来using namespace std让我们能直接写scanf、printf不用加std::前缀。变量里m和n存行列数x存当前读到的像素颜色ans存当前候选的 dominant colorcnt存候选的计数器。第6行读入m和n。这里有个很多人都犯过的错题目第一行先给列数再给行数如果你习惯性地认为先给行数后面循环条件就会出问题。我第 4 节会专门讲这个坑。第7行的循环条件是i m * n直接把所有像素当成一个一维序列处理。这没问题因为摩尔投票只关心元素的值和顺序不关心像素在矩阵里的位置。你完全可以一个for循环螺旋读完整个矩阵。第8行读入一个颜色值x。第9行是核心判断当cnt 0时说明当前没有“有效候选”就把x设为新的候选ans计数器置1然后第10行再把计数器加回去。第10行的写法是一个简洁的合并如果x anscnt加1否则cnt减1。这一行把“遇到相同候选加票遇到不同候选抵消”两个逻辑压缩到了一起。为什么能这么合并因为第9行刚设置了新候选时第10行的x ans必然成立cnt会被加回1而其他情况下cnt要么加要么减逻辑不会乱。第11行输出ans。题目保证存在超过一半的元素所以不需要再验证。3.3 为什么用 scanf / printf 而不是 cin / cout这题有些cin/cout选手会莫名超时其实不是题目的问题而是输入输出流的性能问题。C 的cin默认和 C 的stdio同步为了保证混用scanf和cin时不出错每次cin都要做额外的同步检查。几十万数量级的数据这个开销比scanf慢好几倍。解决方式有两种直接用scanf/printf这也是我代码里的做法。用cin/cout但加上ios::sync_with_stdio(false);和cin.tie(nullptr);关掉同步。本人实测同一种算法用scanf比用没关同步的cin稳定快一倍以上。机试环境不是自己电脑CPU 性能不可控能用scanf就别用cin这是刷题老手的共识。3.4 如果要写工程代码该怎么改12行的竞赛写法追求的是短平快如果放在真实工程项目里我不会这么写。工程上需要考虑用结构体把“候选值 计数器”封装成VoteCounter类暴露feed(int x)和result()方法。输入不再用scanf而是用流式读取或者迭代器适配不同的数据源。不依赖输入保证在投票结束后再遍历一次统计ans的真实出现次数确认是否真的超过一半。对非法输入做防御性校验比如行列数读成0或负数直接报错。看竞赛代码和工程代码其实是两种生物。竞赛追求在约束条件下用最短路径拿满分工程追求可读、可维护、可容错。我们刷题的时候心里要清楚12行代码是用来理解算法的不是用来直接搬到生产环境的。4. 现场实录踩过的坑与性能实测4.1 坑一把 M 和 N 读反了这是我第一次提交就踩的坑。题目说的是第一行给出M和NM是列数、N是行数。我当时想当然地按“M行N列”处理循环条件写成i n * m本身乘积一样所以循环次数没错。但后面验证样例时发现样例输出和自己想的不一样回去一看题才发现把行列语义搞反了。这类细节不会让循环次数出错因为m * n和n * m相等。真正危险的是你后续如果按行列去写二维遍历比如for (int i 0; i n; i) for (int j 0; j m; j)才会暴露问题。实战经验读题先看输入格式里的单位别凭“行优先”的直觉。4.2 坑二用 cin 不关同步流导致超时有一次我在本地跑了样例一切正常提交上去就是最后一个测试点超时。检查了一圈算法没错问题出在cin上。某OJ的测评机比较老几十万次cin加上同步开销直接卡在超时边缘。后来我把cin换成scanf同一份算法逻辑立刻通过。从此我给自己定了一条规矩第一版代码默认用scanf/printf除非题目明确说输入量很小。别把本地运行时间当成评测机运行时间两者性能经常差一个量级。4.3 坑三忽视“保证存在”这个前提如果你把摩尔投票从这道题搬到另一道没有“保证存在”的题直接输出ans就是错的。举个例子序列[1, 2, 3]摩尔投票跑完ans是3但3的出现次数只有1/3并没有超过一半。没有前提保证时它只是“候选者”不是“获胜者”。正确做法是在投票结束后再遍历一次统计ans的数量超过L/2才输出否则输出一个约定的占位符比如-1。我在这道题里没有做校验全靠题目的数据保证。如果你在别的场景复用这个算法一定记得把二次验证加上否则线上会出事故。4.4 三种解法的性能实测记录我在本地用造出来的百万级随机数据分别跑了三种解法得到的结果大致是这样不同机器差异很大看相对关系就好解法时间开销辅助内存mapint, int红黑树很慢中unordered_mapint, int中等较大排序取中位中等偏快较大摩尔投票最快极小为什么摩尔投票能最快因为它对每个元素只做一次比较和一次加减法没有哈希计算没有树旋转没有排序时的大量数据搬动。unordered_map虽然有O(1)均摊时间但那是在忽略哈希冲突和节点分配成本的前提下当数据量变大哈希表频繁扩容、重建桶数组的开销非常可观。我后来又把摩尔投票用在某日志系统中统计高频错误码数据是持续不断的流式输入内存占用始终只有两个整数。哈希表解法在这种流式场景下根本没法用因为你不知道最终会有多少种错误码哈希表会无限膨胀。4.5 一个实用的自测技巧写完代码提交前我会在本地快速验证一下边界M1, N1的情况。只有一个像素时循环跑一次cnt从0变成1ans就是这个像素的值输出正确。再测试M1, N2两个像素颜色相同第一次循环ans设为颜色Acnt1第二次遇到相同颜色cnt2输出A正确。两个像素颜色不同但题目保证存在主导色这种数据本身就不合法不用管。养成这个习惯之后很多低级错误在提交前就能被拦住。竞赛题目不会告诉你边界测试用例自己造几个极端输入永远是最高效的自检方式。5. 延伸摩尔投票的变体与通用模板5.1 从“超过一半”到“超过三分之一”理解了单候选的摩尔投票有一个非常自然的升级版在一个序列里找出所有出现次数超过n/3的元素。因为超过n/3的元素最多只能有2个所以我们需要维护两组候选和计数器。遍历每个元素x时逻辑变成如果x等于候选一候选一计数器加1。否则如果x等于候选二候选二计数器加1。否则如果候选一的计数器为0把候选一设为x计数器置1。否则如果候选二的计数器为0把候选二设为x计数器置1。否则两个候选的计数器都减1表示同时抵消掉一组。遍历结束后两个候选里可能出现答案但还是要靠第二次遍历统计真实次数来确认。这个版本的时间复杂度依然是O(L)空间依然是O(1)。对应到代码大概是这样一个模板vectorint findMajority(vectorint nums) { int c1 0, c2 0, cnt1 0, cnt2 0; for (int x : nums) { if (x c1) cnt1; else if (x c2) cnt2; else if (cnt1 0) { c1 x; cnt1 1; } else if (cnt2 0) { c2 x; cnt2 1; } else { cnt1--; cnt2--; } } // 第二遍验证 vectorint res; int t1 0, t2 0; for (int x : nums) { if (x c1) t1; else if (x c2) t2; } if (t1 nums.size() / 3) res.push_back(c1); if (t2 nums.size() / 3) res.push_back(c2); return res; }5.2 通用化找出现次数超过 n/k 的元素把这个问题再推一步如果要求找出现次数超过n/k的元素答案最多有k-1个。用k-1组候选和计数器跑摩尔投票每遇到一个不属于任何候选的新值就把所有候选的计数器都减一。算法仍然是线性的只是候选数组长度变成了O(k)。这个通用形式虽然在实际面试题里出现频率不算高但它说明了一件事摩尔投票不是一个孤立的“技巧”而是一整套“用抵消思想解决频次问题”的算法家族。理解了原始版本后面的变体都不是死记硬背而是顺其自然的推导。5.3 流式数据与工程场景中的应用摩尔投票最迷人的地方在于它是一个在线算法。什么叫在线就是你不必等到全部数据到齐每来一个数据你都能实时更新候选状态数据流结束时答案已经在手上了。这个性质在日常工程里非常有用。比如一个网关要统计过去24小时内请求数最高的某个错误码但请求流量每秒钟几万条你不可能把全量日志存下来再排序。这时候摩尔投票就可以做到只维护两个变量持续“抵消”随时给出当前最能“压住场子”的错误码。当然工程上往往还需要加上时间窗口、衰减权重等更复杂的机制但核心的“抵消”思想就这样沿用了下来。学算法的时候我会刻意思考“这个算法如果接到一个流式SDK里怎么用”这种思维转换能让人对算法的理解深一层而不是只停留在解OJ题。5.4 刷题复盘12行的意义不是压行最后想聊点刷题之外的东西。很多人看到“12行AC”的第一反应是“代码真短”但代码短不是目的它只是一个结果。真正有价值的不是行数而是那行cnt (x ans) ? 1 : -1;背后压缩掉的大量思维过程。我见过一些刷题很猛的同学一上来就背模板各种高级数据结构信手拈来但碰到一道20分的简单题反而习惯性地上unordered_map。这不是能力问题而是思维惯性在作祟。刷题训练的不是“会多少算法”而是“看到条件能不能想到最合适的算法”。“超过一半”这个词一出来条件反射应该就是摩尔投票和排序取中位而不是把题目和哈希表绑定死。经过这道题我最大的收获是养成了一个习惯拿到任何题目先圈出所有约束条件特别是“保证”“不超过”“正好”这类词然后问自己一句——这个条件能不能让问题变得更简单能避开冗余的数据结构时就避开。这种习惯让我的代码越写越短而且每段删除都不是为了炫技是真的想清楚了“这部分计算是多余的”。如果你正在备考机试建议把这题反复做三遍第一遍用unordered_map第二遍用排序取中位第三遍用摩尔投票。三遍代码都跑通之后你会发现同样一道20分的题三种解法背后的思考路径完全不一样而这种“路径差异”才是算法题真正值20分的地方。