外观
从 O(n) 空间到 O(1)：摩尔投票法超半数机型统计实战
问题背景：如何在海量机型上报中找出“绝对多数”
在设备分析、日志聚合、投票统计等场景中，经常会遇到一类问题：给定一长串机型标识，判断是否存在某个机型出现次数超过总样本数的一半；如果存在，返回该机型。
最直观的做法是使用哈希表计数：遍历一次数组，用字典记录每个机型出现次数，再找出次数满足 count > n / 2 的机型。这个方案时间复杂度为 O(n)，但空间复杂度也是 O(n)。当日志数据量达到千万级，或者统计逻辑运行在内存受限的端上设备时，额外哈希表会带来明显压力。
Boyer-Moore Majority Vote Algorithm，即摩尔投票法，正是解决“超半数元素”问题的经典算法。它利用多数元素“数量超过其余所有元素之和”的性质，通过不同元素之间的对抗抵消，在 O(1) 空间内完成候选筛选。
方案对比：哈希计数、排序与摩尔投票
哈希表计数
优点是逻辑简单、容易验证，不仅能找超半数元素，也能统计任意频率。缺点是需要保存所有不同元素的计数，空间复杂度为 O(n)。
排序法
如果某个元素出现次数超过 n / 2，排序后它一定会占据数组中间位置，因此返回 nums[n // 2] 即可。代码很短，但排序通常需要 O(n log n) 时间，并且会修改或复制原数组。
摩尔投票法
摩尔投票法分为两个阶段：
- 对抗阶段：维护候选元素
candidate和生命值count；遇到相同候选则count + 1，遇到不同元素则count - 1；当count归零时，更换候选。 - 验证阶段：重新统计候选元素出现次数，确认它是否真的超过半数。
需要特别注意：如果题目没有保证多数元素一定存在，第二阶段不能省略。因为摩尔投票只会选出“最后存活的候选”，但这个候选未必满足超半数条件。
核心思想：为什么“抵消”不会淘汰多数元素
假设真正的多数元素为 m，它出现次数大于 n / 2。投票过程中，每一次 count - 1 都可以理解为：用一个非 m 元素与当前阵营中的一个元素配对删除。
即使最坏情况下，所有非 m 元素都专门用来抵消 m，非 m 元素总数仍然少于 m 的数量。因此，所有配对结束后，至少还会剩下一个 m。这就是摩尔投票法最关键的正确性基础。
不过，这个结论只在“多数元素确实存在”时成立。例如数组 [A, B, C] 中没有任何元素超过半数，但投票阶段仍可能留下 C。所以工程实现中应统一保留验证步骤，避免把“最后候选”误判成“多数元素”。
实操步骤：统计上报次数超半数的机型
下面使用 Python 实现一个可直接运行的示例。函数接收机型列表，返回出现次数超过一半的机型；如果不存在，则返回 None。
python
from typing import List, Optional
def find_majority_model(models: List[str]) -> Optional[str]:
"""返回出现次数超过 len(models) / 2 的机型；不存在则返回 None。"""
if not models:
return None
# 第一阶段：对抗抵消，选出存活候选
candidate = None
count = 0
for model in models:
if count == 0:
# 当前阵营已被完全抵消，选择新候选
candidate = model
count = 1
elif model == candidate:
# 同类机型加入阵营
count += 1
else:
# 不同机型对抗，生命值减一
count -= 1
# 第二阶段：验证候选是否真的超过半数
candidate_count = sum(model == candidate for model in models)
if candidate_count > len(models) // 2:
return candidate
return None
# 可运行测试
if __name__ == "__main__":
samples = [
["iPhone15", "Mi14", "iPhone15", "iPhone15", "Pixel8"],
["A", "B", "C"],
[],
]
for sample in samples:
print(sample, "=>", find_majority_model(sample))运行结果中，第一个列表的多数机型是 iPhone15；第二个列表没有超半数机型，因此返回 None；空列表同样返回 None。
复杂度分析
- 时间复杂度：
O(n)。第一阶段扫描一次数组，第二阶段最多再扫描一次，总计线性时间。 - 空间复杂度：
O(1)。整个过程只使用candidate、count、candidate_count等常数级变量。 - 稳定性：不会修改输入数组，也不需要额外维护哈希表。
JavaScript 版本：适合前端日志 SDK 内嵌
如果统计逻辑运行在浏览器或前端监控 SDK 中，也可以使用 JavaScript 实现：
javascript
/**
* 返回出现次数超过数组长度一半的机型
* @param {string[]} models 机型列表
* @returns {string | null}
*/
function findMajorityModel(models) {
if (models.length === 0) return null;
let candidate = null;
let count = 0;
// 摩尔投票阶段
for (const model of models) {
if (count === 0) {
candidate = model;
count = 1;
} else if (model === candidate) {
count++;
} else {
count--;
}
}
// 二次验证阶段
const candidateCount = models.filter(
(model) => model === candidate
).length;
return candidateCount * 2 > models.length ? candidate : null;
}
console.log(findMajorityModel(["iPhone15", "Mi14", "iPhone15", "iPhone15"]));
// 输出：iPhone15这里使用 candidateCount * 2 > models.length 判断严格超过半数，可以避免 JavaScript 中整数与浮点数边界处理带来的歧义。
扩展理解：摩尔投票与多候选问题
标准摩尔投票法解决的是“出现次数超过 n / 2”的问题。如果题目改成“出现次数超过 n / 3”，最多可能有两个答案，此时可以维护两个候选和两个计数器，再进行统一验证。
但不要把摩尔投票机械套用到任意 Top-K 频率问题中。它的本质不是通用频率统计，而是利用严格比例条件进行阵营抵消。若需求是出现次数最多的前 K 个机型，或者阈值不是固定比例，堆、哈希表、分桶等方案通常更合适。
避坑总结：实战中最容易出错的 4 个点
1. 忘记验证候选，把无多数数组误判为有结果
错误现象：输入 [A, B, C] 时，投票阶段可能返回 C，业务层直接认为 C 是多数机型。
修正方法：无论题目是否暗示存在答案，工程代码都建议二次扫描，检查候选计数是否满足 count > n / 2。
2. 把“超过半数”写成“大于等于半数”
错误现象：数组长度为 4，某机型出现 2 次，代码使用 count >= n / 2，错误地将其判定为多数元素。
修正方法：严格多数必须满足 count > n / 2。在整数写法中推荐使用 count * 2 > n，语义更直接。
3. 候选更换顺序错误，导致同一次扫描重复计票
错误现象：当 count == 0 时，有些实现先把 count 加一，却没有更新 candidate；或者先进入 model == candidate 判断，再处理归零逻辑，造成候选状态混乱。
修正方法：每轮循环优先判断 count == 0，此时直接设置 candidate = model、count = 1，并进入下一轮；只有 count > 0 时才比较当前元素与候选。
4. 空数组或空值输入未处理
错误现象：空列表时 candidate 保持为语言中的空值，后续验证阶段可能返回 null、undefined，甚至抛出异常。
修正方法：函数入口先判断输入是否为空；若业务数据允许 None 或空字符串作为合法机型，还应明确这些值是否参与统计，避免把“无候选”和“候选就是空字符串”混为一谈。
结语
摩尔投票法的价值不只是解决一道经典算法题，更重要的是提供了一种“对抗抵消”的建模方式：当目标阵营严格强于其他所有阵营之和时，就不必保存完整计数，而可以用常数状态记录最终幸存者。
在超半数机型统计、主节点选举、异常版本确认等工程场景中，只要先明确严格多数条件，并补上候选验证，就能用 O(n) 时间和 O(1) 空间得到可靠结果。
免责声明
本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。