尧图网站建设 尧图网络
  • 首页
  • 关于我们
  • 服务项目
  • 案例展示
  • 建站流程
  • 资讯中心
  • 联系我们
首页/资讯中心/详情

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

摩尔投票法:线性时间寻找多数元素的优雅算法
📅 发布时间:2026/7/2 4:46:45

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

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


一、算法核心思想

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

  1. 维护一个候选元素candidate和一个计数器count,初始count = 0。
  2. 遍历数组每个元素num:
  • 若count == 0,则将candidate设为当前num。
  • 若num == candidate,则count++,否则count--。
  1. 遍历结束后,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我们得到频次分布:

元素出现次数占比
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};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可维护两个候选及对应计数,额外增加一次验证
非整数倍阈值通过调整"抵消"条件,可适配不同比例要求
数据流场景算法天然支持流式处理,只需常量内存即可实时输出当前候选

六、总结

摩尔投票法以极其精妙的“抵消”思路,用常量空间解决了看似需要哈希表的问题。它不仅是算法竞赛中的"背板题",更体现了通过问题特性优化资源的工程思维。

当你下次面对"多数元素"问题时,不妨用这短短几行代码,展现你的算法功底。


✨记住:多数元素的票数优势,足以让它在抵消浪潮中最后屹立不倒。

相关新闻

  • AI落地五大硬核挑战与可验证工程解决方案
  • Day1 AI 到底淘汰谁?普通人最真实的生存真相
  • 分布式、服务化的ERP系统架构设计

最新新闻

  • 第08篇:FlashAttention 与高效注意力——把 O(n²) 显存打回 O(n) 的工程奇迹
  • LibreSignage:零成本构建专业数字标牌系统的开源利器
  • 1984–2026全国村级居民点数据|300W+点位|村点分布SHP矢量数据|长时序人居聚落
  • 流体动力学中的机器学习:批判性评述
  • 上海办公升降桌设备多推荐哪款
  • 基于TM4C123GH6PZ的智能RGB LED灯光控制系统开发

日新闻

  • Python Playwright录制功能:从零到一构建自动化测试脚本
  • 如何用开源工具永久保存你心爱的小说:novel-downloader全攻略
  • In-Context Learning不是教知识,而是模式对齐:从5个示例到100个工业级样本的真相

周新闻

  • Windows字体自定义终极方案:No!! MeiryoUI完全指南
  • Deepin Boot Maker:告别命令行,3分钟制作Linux启动盘的智能解决方案
  • Plain Craft Launcher 2:重新定义你的Minecraft游戏体验

月新闻

  • 2026年6月公司网站搭建最新热门渠道测评:四大低成本/零代码平台对比+避坑
  • 【Linux】Linux arm 编译QT程序,出现expected “}“报错
  • 【MATLAB例程】四基站二维AOA定位与距离辅助增强对比仿真。基于角度观测和测距修正的固定目标平面定位精度分析

关于尧图

  • 公司简介
  • 团队介绍
  • 企业文化
  • 荣誉资质

服务项目

  • 定制开发
  • 电商建站
  • UI 设计
  • 运维服务

快速链接

  • 案例展示
  • 建站流程
  • 常见问题
  • 资讯中心

联系方式

  • 📍北京市朝阳区互联网产业园 A 座 10 层
  • 📞400-888-8888
  • ✉️contact@rkmt.cn
  • 🕐周一至周日 9:00-21:00

© 2024 北京尧图网络科技有限公司 版权所有 | 京 ICP 备 XXXXXXXX 号