摩尔投票法详解
一、摩尔投票法是什么
摩尔投票法是一种高效的线性时间、常数空间算法,专门用于求解 无序数组中出现次数超过 n/2 的元素(也叫绝对众数),同时可以扩展到求解出现次数超过 n/k 的元素。 核心优势:
本文详细介绍了摩尔投票法,这是一种用于在无序数组中查找出现次数超过一半元素的线性时间、常数空间算法。文章阐述了算法的核心抵消思想、执行步骤及验证必要性,提供了基础版和简化版的 Python 代码实现。此外,还讲解了如何扩展该算法以查找出现次数超过 n/k 的元素,并对比了其与哈希表法的优劣及适用场景,适合算法学习与面试准备。

摩尔投票法是一种高效的线性时间、常数空间算法,专门用于求解 无序数组中出现次数超过 n/2 的元素(也叫绝对众数),同时可以扩展到求解出现次数超过 n/k 的元素。 核心优势:
摩尔投票法的核心可以拆解为 「抵消」和「计数」 两个关键步骤,逻辑极其简洁:
candidate 和一个计数变量count。
count == 0,说明当前没有候选众数,将当前元素设为 candidate;candidate,则 count += 1(候选众数的支持数 +1);candidate,则 count -= 1(不同元素两两抵消,支持数 -1)。candidate 只是可能的众数,需要再次遍历数组,统计其真实出现次数,确认是否超过 n/2。
算法的本质是利用「多数元素的压倒性优势」:即使每次抵消一对不同元素,最终剩下的元素一定是绝对众数(如果存在的话)。
举个例子:数组 [2,2,1,1,1,2,2],绝对众数是 2(出现 5 次,超过 7/2=3.5)。遍历过程中,2 和 1 不断抵消,但 2 的数量更多,最终会成为候选值。
以求解「数组中出现次数超过 n/2 的元素」为例,步骤标准化,无任何变种:
candidate = None,count = 0;num;count == 0,令 candidate = num;num == candidate,count += 1,否则 count -= 1;candidate 在数组中的出现次数 total;total > n/2,返回 candidate,否则返回 None(无绝对众数)。def majority_element(nums):
# 步骤 1:抵消阶段,找候选众数
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
# 步骤 2:验证阶段,确认是否为绝对众数
total = 0
for num in nums:
if num == candidate:
total += 1
return candidate if total > len(nums) // 2 else None
如果题目明确说明「数组中一定存在绝对众数」,可以省略验证阶段,直接返回候选值:
def majority_element_simple(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
# 测试 1:存在绝对众数
nums1 = [2,2,1,1,1,2,2]
print(majority_element(nums1)) # 输出 2
# 测试 2:不存在绝对众数
nums2 = [1,2,3,4,5]
print(majority_element(nums2)) # 输出 None
# 测试 3:简化版(假设存在)
print(majority_element_simple(nums1)) # 输出 2
摩尔投票法可以扩展到求解 数组中出现次数超过 n/k 的所有元素,这是面试高频进阶考点,核心逻辑是「最多有 k-1 个元素满足条件」。
candidates,存储最多 k-1 个候选元素及其计数;def majority_element_k(nums, k=3):
# 步骤 1:抵消阶段,最多 k-1 个候选
candidates = {}
for num in nums:
if num in candidates:
candidates[num] += 1
elif len(candidates) < k - 1:
candidates[num] = 1
else:
# 所有候选计数 -1,删除计数为 0 的
to_remove = []
for key in candidates:
candidates[key] -= 1
if candidates[key] == 0:
to_remove.append(key)
for key in to_remove:
del candidates[key]
# 步骤 2:验证阶段
n = len(nums)
res = []
for key in candidates:
total = nums.count(key)
if total > n // k:
res.append(key)
return res
# 测试:找超过 n/3 的元素
nums = [3,2,3,1,1,2,2]
print(majority_element_k(nums)) # 输出 [2,3]
candidate 和 count,空间复杂度为常数级;这是最容易踩的坑!如果数组中不存在绝对众数,算法也会返回一个候选值,必须通过验证才能确认结果。
例如数组 [1,2,3],算法会返回 3,但 3 的出现次数只有 1 次,不满足超过 3/2=1.5 的条件。
摩尔投票法仅适用于求解出现次数超过 n/k 的元素,如果题目要求「出现次数最多的元素」(不要求超过 n/k),则需要用哈希表统计频次,无法使用该算法。
求解超过 n/k 的元素时,最多有 k-1 个元素满足条件,这是数学定理。 例如 k=2 时最多 1 个,k=3 时最多 2 个,利用这个性质可以限制候选字典的大小。
无论数组的遍历顺序如何,最终得到的候选值都是相同的(如果存在绝对众数),因为抵消的本质是「不同元素两两消除」,与顺序无关。
两者都是求解众数问题的常用方法,面试中经常作为对比考点,必须牢记区别和适用场景:
| 特性 | 摩尔投票法 | 哈希表法 |
|---|---|---|
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(1)(基础版) | O(n) |
| 适用场景 | 找超过 n/k 的元素 | 找任意频次的元素 |
| 优点 | 空间效率极高,无需额外存储 | 逻辑简单,适用范围广 |
| 缺点 | 适用场景有限,需要验证 | 空间开销大,数据量大时内存紧张 |

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具,curl 转代码在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online