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

摩尔投票法

news 2025/9/22 16:31:03

0、参考资料（讲解视频及博客等）

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

一、应用场景

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

二、核心思想 / 步骤

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

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

三、代码模板与测试

代码模板 (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)（原地排序）	仅适用于 “超半数” 场景（排序后中间元素必为目标）	时间开销高（排序），但无需额外验证。