摩尔投票法：线性时间寻找多数元素的优雅算法

2026/7/2 4:46:45

摩尔投票法：线性时间寻找多数元素的优雅算法

在算法面试和数据处理中，我们常遇到一类问题：给定一个长度为n的数组，找出其中出现次数超过n/2的“多数元素”（众数）。若不做特殊限制，最直观的做法是用哈希表统计频次，时间复杂度O(n)，空间复杂度O(n)。但能否在O(n)时间 +O(1)空间内完成？答案是肯定的——这就是摩尔投票法（Boyer–Moore Majority Vote Algorithm）。

一、算法核心思想

摩尔投票法巧妙地将“投票”与“抵消”机制结合，其逻辑极为简洁：

维护一个候选元素candidate和一个计数器count，初始count = 0。
遍历数组每个元素num：

若count == 0，则将candidate设为当前num。
若num == candidate，则count++，否则count--。

遍历结束后，candidate即为多数元素（若确实存在）。

这背后的直观理解是：不同的元素两两配对抵消，最终剩下的就是出现次数过半的那个"胜者"。

二、代码实现解析

以下 Java 方法完美实现了该算法：

publicstaticintgetMaxCount(int[]ans){intcount=0;inttemp=0;for(intnum:ans){if(count==0){temp=num;}count+=(num==temp)?1:-1;}returntemp;}

逐行解读

行/操作	说明
`count == 0`	意味着之前候选元素已被完全抵消，重新选定当前元素为候选
`num == temp`→`+1`	当前元素与候选相同则加一票
`num != temp`→`-1`	不同则减一票（相当于一次抵消）
最终`temp`	经过多轮抵消后存活的候选元素

为何不必二次验证？

重要前提：该算法仅在题目保证多数元素一定存在时，返回结果必定正确。若多数元素不存在（如数组[1, 2, 3]），算法仍会返回一个值，但该值并非真正众数。因此，在实际工程中，如果无法确保输入条件，通常需要再遍历一次数组验证候选者的频次是否超过n/2。

三、复杂度与适用场景

项目	指标
时间复杂度	`O(n)`，仅一次遍历
空间复杂度	`O(1)`，仅两个变量
适用场景	流式数据、单次遍历、内存受限环境

典型题目

LeetCode 169— 多数元素
面试高频手写题

四、示例运行分析

int[]ints={2,1,6,5,6,1,1,1,1,1,1,4,0};

通过printArrayDetail我们得到频次分布：

元素	出现次数	占比
1	7	≈ 53.85%
其余元素	6	≈ 46.15%

元素1出现 7 次，占比约53.85%，超过半数。

算法遍历过程

初始候选 2 → 被后续 1、6、5 等逐步抵消 → 最终候选锁定为 1 ✅

与统计结果完全吻合。你贴心地打印了每个元素的详细计数和百分比，这对调试和理解数据分布很有帮助。

完整代码

importjava.util.HashMap;importjava.util.Map;publicclassMaxCount{publicstaticvoidmain(String[]args){int[]ints={2,1,6,5,6,1,1,1,1,1,1,4,0};intmaxCount=getMaxCount(ints);printArrayDetail(ints);System.out.printf("Result: %s%n",maxCount);}publicstaticintgetMaxCount(int[]ans){intcount=0;inttemp=0;for(intnum:ans){if(count==0){temp=num;}count+=(num==temp)?1:-1;}returntemp;}publicstaticvoidprintArrayDetail(int[]ans){Map<Integer,Integer>map=newHashMap<>();for(intnum:ans){map.put(num,map.getOrDefault(num,0)+1);}map.forEach((k,v)->{Stringformatted=String.format("* Element(%s) - Count(%s) - Percent(%.2f%%)",k,v,v*100.0/ans.length);System.out.println(formatted);});}}

运行结果：

F:\code26\env\jdk\bin\java.exe -javaagent:F:\program_files\idea-2026.1.win\lib\idea_rt.jar=10378 -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath F:\code26\test-java\out\production\test-java MaxCount * Element(0) - Count(1) - Percent(7.69%) * Element(1) - Count(7) - Percent(53.85%) * Element(2) - Count(1) - Percent(7.69%) * Element(4) - Count(1) - Percent(7.69%) * Element(5) - Count(1) - Percent(7.69%) * Element(6) - Count(2) - Percent(15.38%) Result: 1 Process finished with exit code 0

五、扩展思考：摩尔投票法的变体

变体	说明
出现次数 > n/3	可维护两个候选及对应计数，额外增加一次验证
非整数倍阈值	通过调整"抵消"条件，可适配不同比例要求
数据流场景	算法天然支持流式处理，只需常量内存即可实时输出当前候选