Boyer-Moore投票算法适合找众数，因其仅需O(1)空间和O(n)时间，且不预设众数存在，核心是候选抵消逻辑；但必须二次遍历验证候选是否真满足出现次数＞n/2，否则结果不可靠。
为什么 Boyer-Moore 投票算法适合找众数
它只用 O(1) 空间、O(n) 时间，且不要求提前知道众数是否存在——特别适合处理超大数组或流式数据。但注意：该算法**只保证在众数存在时返回它**；如果不存在众数，结果不可靠，必须二次验证。
核心逻辑是“抵消”：用一个候选 candidate 和计数器 count 遍历数组，遇到相同值就 count += 1，不同就 count -= 1；count 归零就换候选。
- 它不统计频次，只做相对多数推断
- 对非众数元素多的数组（如
[1,2,3]）会返回任意一个值，无意义 - 必须搭配一次额外遍历验证候选是否真为众数
Python 实现中的关键细节和易错点
写错 count == 0 的判断时机、漏掉验证步骤、混淆“出现次数 > n/2”和“出现次数 ≥ n/2”，都会导致错误结果。
-
count初始设为0，不是1；第一次赋值candidate必须发生在count == 0之后 - 验证阶段必须重新遍历原数组统计频次，不能复用第一遍的
count - 边界情况：空数组要提前返回
None；单元素数组直接返回该元素 - Python 中整除用
//，但判断条件是freq > len(nums) // 2（不是>=），因为题目定义众数为「严格超过一半」
def majorityElement(nums):
if not nums:
return None
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x
count = 1
else:
count += 1 if x == candidate else -1
# 验证
freq = sum(1 for x in nums if x == candidate)
return candidate if freq > len(nums) // 2 else None
和 collections.Counter 对比的实际影响
用 Counter 写法简洁：Counter(nums).most_common(1)[0][0]，但空间复杂度是 O(n)，且无法提前终止——哪怕前两个元素就是众数，它仍要扫完整个数组并建哈希表。
macOS UI 自动化技能包 —— 用 Python 控制你的 Mac
下载
让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限
立即学习“Python免费学习笔记（深入）”；
- 内存敏感场景（如嵌入式、大数据流）必须用
Boyer-Moore -
Counter可自然支持找“前 K 多”元素，Boyer-Moore仅适用于 K=1 且满足众数定义的情况 - 若需同时获取众数和频次，
Boyer-Moore多一次遍历也比Counter节省内存；但若后续还要查其他元素频次，Counter更划算
当数组不保证存在众数时，验证步骤不能省
这是最常被跳过的一步。例如输入 [1,2,2,3,3]（长度 5，任一值最多出现 2 次），Boyer-Moore 第一遍可能返回 3 或 2（取决于遍历顺序），但两者都不满足「出现 > 2.5 次」。没有验证，就会静默返回错误答案。
- 验证必须独立进行，不能依赖第一遍的
count值——那只是抵消过程的中间状态，不反映真实频次 - 验证可用
nums.count(candidate)，但对大数组效率略低；推荐用生成器表达式 +sum，避免构造新列表 - 某些面试题会明确说“保证众数存在”，此时可省验证；但生产代码一律保留，除非有强契约保障
实际用的时候，别图省事跳过验证——那个 sum(1 for x in nums if x == candidate) 就是最后一道保险。
