本文详细介绍了摩尔投票法，这是一种用于在无序数组中查找出现次数超过一半元素的线性时间、常数空间算法。文章阐述了算法的核心抵消思想、执行步骤及验证必要性，提供了基础版和简化版的 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