当前位置: 首页 > news >正文

摩尔投票法

0、参考资料(讲解视频及博客等)

  • 本人水平有限,如有错误,恳请指正
  • 讲解视频:【【算法】摩尔投票法】

一、应用场景

  • 典型应用场景:在一个数组中,寻找出现次数超过总元素数一半的元素(即 “主元素”);也可扩展到寻找出现次数超过 kn​ 的元素(需结合多候选抵消逻辑)。
  • 场景特点:数组规模大,要求时间复杂度尽可能低(线性时间)、空间复杂度尽可能小(常数空间),避免额外存储大量计数信息。

二、核心思想 / 步骤

摩尔投票法的核心是 “计数抵消”:利用 “多数元素的数量优势”,让不同元素相互抵消,最终筛选出候选元素,再通过验证确认是否为目标。
分为两个核心阶段:

  1. 候选元素筛选
    • 初始化:选数组第一个元素为候选元素,计数 count = 1(表示候选的 “剩余优势次数”)。
    • 遍历数组后续元素:
      • 若当前元素与候选元素相同:count++(强化候选的 “数量优势”)。
      • 若当前元素与候选元素不同:
        • 若 count > 0count--(用候选的 “优势次数” 抵消当前不同元素)。
        • 若 count == 0:更换候选元素为当前元素,重置 count = 1(原候选已被完全抵消,新候选重新积累优势)。
  2. 候选元素验证
    • 遍历结束后,候选元素是 “可能的多数元素”,但需再次遍历数组,统计其实际出现次数。
    • 若实际次数超过总元素数的一半,则确认为主元素;否则说明不存在主元素(避免抵消过程中的误判)。

三、代码模板与测试

代码模板 (C 语言为例)

int majorityElement(int* nums, int numsSize) {int candidate = nums[0]; // 初始化候选元素int count = 1;           // 候选元素的计数// 阶段1:筛选候选元素for (int i = 1; i < numsSize; i++) {if (nums[i] == candidate) {//为候选人得票count++;} else {//竞争对手if (count > 0) {count--;//冲突抵消} else {//cnt = 0,更换候选人candidate = nums[i];count = 1;}}}// 阶段2:验证候选元素(若题目确保存在主元素,可省略此阶段)int verifyCount = 0;for (int i = 0; i < numsSize; i++) {if (nums[i] == candidate) {verifyCount++;}}return (verifyCount > numsSize / 2) ? candidate : -1; // 存在返回候选,否则返回-1
}

样例

寻找数组中的主元素(出现次数超过一半的元素)
输入nums = {0, 5, 5, 3, 5, 7, 5, 5}(长度为 8,5 出现 5 次,超过 8/2=4 次)
输出5

#include <stdio.h>int majorityElement(int* nums, int numsSize) {int candidate = nums[0];int count = 1;for (int i = 1; i < numsSize; i++) {if (nums[i] == candidate) count++;else {if (count > 0) count--;else {candidate = nums[i];count = 1;}}}int verify = 0;for (int i = 0; i < numsSize; i++) if (nums[i] == candidate) verify++;return verify > numsSize / 2 ? candidate : -1;
}int main() {int nums[] = {0, 5, 5, 3, 5, 7, 5, 5};int size = sizeof(nums) / sizeof(nums[0]);int result = majorityElement(nums, size);printf("主元素:%d\n", result); // 输出:5return 0;
}

四、优化与同类算法对比

优化方案

  • 题目明确保证存在主元素(如 LeetCode 169 题),可直接省略 “验证阶段”,遍历一次即可返回候选元素,此时时间复杂度为 O(n),空间复杂度为 O(1)(最优)。
  • 扩展场景(找出现次数超过 kn​ 的元素):需维护 k−1 个候选及对应计数,逻辑类似 “多候选相互抵消”,最终再验证每个候选的实际次数。

算法对比 / 复杂度分析

算法 时间复杂度 空间复杂度 适用场景 优缺点
摩尔投票法 O(n) O(1) 找 “超半数” 或 “超 kn​” 元素 时间、空间最优;但仅适用于 “数量优势类” 问题,通用性弱。
哈希表计数 O(n) O(n) 任意频率统计 通用但空间开销大,哈希表存储所有元素的计数。
排序后取中间 O(nlogn) O(1)(原地排序) 仅适用于 “超半数” 场景(排序后中间元素必为目标) 时间开销高(排序),但无需额外验证。

五、相关 LeetCode 题目推荐

  • LeetCode 169. 多数元素(基础应用,保证存在主元素)
  • LeetCode 229. 多数元素 II(扩展应用,找出现次数超过 3n​ 的元素)
  • LeetCode 面试题 17.10. 主要元素(需验证主元素是否存在)
  • 408统考2013年真题
http://www.hskmm.com/?act=detail&tid=13501

相关文章:

  • 基于STM32平台的ADS1292心电采集驱动程序
  • ProcessPoolExecutor VS ThreadPoolExecutor 进程池对比线程池
  • 深入解析MS12-020关键漏洞CVE-2012-0002:远程桌面协议的安全风险与缓解方案
  • 鸿蒙项目实战(九):get请求参数的处理
  • allegro17.4 布线鼠标拖动变成了ployline,重启后恢复,记得有地方设置但是一时找不到在哪儿了,有知道的网友吗?
  • 20250806_信安一把梭_test
  • 专业 RAW 图像处理利器!DxO PhotoLab 让你的照片质感飙升
  • mysql时间转字符串,自定义格式将日期时间值转换为字符串
  • 其他与其它的区别
  • 一天一款实用的AI工具,第2期,AI摘要生成工具
  • 邀您参加丨云栖大会中企出海技术分论坛
  • 压测指标和结果分析
  • 指令流水线
  • nuget控制台乱码的解决办法
  • 中文乱码速查表
  • .NET驾驭Word之力:结构化文档元素操作
  • 行稳、致远 | 技术驱动下的思考感悟
  • 在控制台执行这段代码可以列出所有::selection规则
  • JDK从8升级到21的问题集
  • 超前探展!2025 云栖大会朋友圈晒图必备
  • 进程池
  • AutoCAD 2025 CAD 安装包中文永久免费免激活破解版下载及详细安装教程
  • 报表神器Stimulsoft再升级!Stimulsoft Reports、Dashboards 和 PDF Forms 2025.4 即将发布!
  • 题解:AT_agc027_e [AGC027E] ABBreviate
  • 【PostgreSQL 17】11 窗口函数
  • 商家列表管理与公众号二维码绑定​,方便对用户进行消息通知提醒
  • linux权限细化管理的三种方法:polkit sudoer doas做权限管理
  • mysql常用
  • 国产化Excel开发组件Spire.XLS教程:Python 写入 Excel 文件,数据写入自动化实用指南
  • Ansible的安装和使用