摩尔投票法线性时间寻找多数元素的优雅算法在算法面试和数据处理中我们常遇到一类问题给定一个长度为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){intcount0;inttemp0;for(intnum:ans){if(count0){tempnum;}count(numtemp)?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我们得到频次分布元素出现次数占比17≈ 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};intmaxCountgetMaxCount(ints);printArrayDetail(ints);System.out.printf(Result: %s%n,maxCount);}publicstaticintgetMaxCount(int[]ans){intcount0;inttemp0;for(intnum:ans){if(count0){tempnum;}count(numtemp)?1:-1;}returntemp;}publicstaticvoidprintArrayDetail(int[]ans){MapInteger,IntegermapnewHashMap();for(intnum:ans){map.put(num,map.getOrDefault(num,0)1);}map.forEach((k,v)-{StringformattedString.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.jar10378 -Dfile.encodingUTF-8 -Dsun.stdout.encodingUTF-8 -Dsun.stderr.encodingUTF-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可维护两个候选及对应计数额外增加一次验证非整数倍阈值通过调整抵消条件可适配不同比例要求数据流场景算法天然支持流式处理只需常量内存即可实时输出当前候选六、总结摩尔投票法以极其精妙的“抵消”思路用常量空间解决了看似需要哈希表的问题。它不仅是算法竞赛中的背板题更体现了通过问题特性优化资源的工程思维。当你下次面对多数元素问题时不妨用这短短几行代码展现你的算法功底。✨记住多数元素的票数优势足以让它在抵消浪潮中最后屹立不倒。
摩尔投票法：线性时间寻找多数元素的优雅算法
摩尔投票法线性时间寻找多数元素的优雅算法在算法面试和数据处理中我们常遇到一类问题给定一个长度为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){intcount0;inttemp0;for(intnum:ans){if(count0){tempnum;}count(numtemp)?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我们得到频次分布元素出现次数占比17≈ 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};intmaxCountgetMaxCount(ints);printArrayDetail(ints);System.out.printf(Result: %s%n,maxCount);}publicstaticintgetMaxCount(int[]ans){intcount0;inttemp0;for(intnum:ans){if(count0){tempnum;}count(numtemp)?1:-1;}returntemp;}publicstaticvoidprintArrayDetail(int[]ans){MapInteger,IntegermapnewHashMap();for(intnum:ans){map.put(num,map.getOrDefault(num,0)1);}map.forEach((k,v)-{StringformattedString.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.jar10378 -Dfile.encodingUTF-8 -Dsun.stdout.encodingUTF-8 -Dsun.stderr.encodingUTF-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可维护两个候选及对应计数额外增加一次验证非整数倍阈值通过调整抵消条件可适配不同比例要求数据流场景算法天然支持流式处理只需常量内存即可实时输出当前候选六、总结摩尔投票法以极其精妙的“抵消”思路用常量空间解决了看似需要哈希表的问题。它不仅是算法竞赛中的背板题更体现了通过问题特性优化资源的工程思维。当你下次面对多数元素问题时不妨用这短短几行代码展现你的算法功底。✨记住多数元素的票数优势足以让它在抵消浪潮中最后屹立不倒。
