摩尔投票法：寻找众数的终极利器（LeetCode 169 深度解析）

在数据海洋中寻找真正的王者，摩尔投票法用O(1)空间征服了众数搜索的难题

问题背景：LeetCode 169 多数元素

题目描述：
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素（假设数组非空且总存在多数元素）。

示例：
输入：nums = [2,2,1,1,1,2,2]
输出：2

常规解法与局限

1. 哈希表计数（时间复杂度O(n)，空间复杂度O(n)）：

def majorityElement(nums): counts = {} for num in nums: counts[num] = counts.get(num, 0) + 1 if counts[num] > len(nums)//2: return num

2. 排序法（时间复杂度O(n log n)，空间复杂度O(1)）：

def majorityElement(nums): nums.sort() return nums[len(nums)//2]

痛点：当数据量达到GB/TB级别时，哈希表的空间开销和排序的时间开销变得不可接受！

摩尔投票法：Boyer-Moore 的智慧结晶

核心思想：通过相互抵消的策略，在常数空间内找出众数

算法步骤：

1. 初始化候选元素 candidate 和计数器 count = 0
2. 遍历数组：
   • 当 count == 0 时，选择当前元素作为新候选
   • 遇到相同元素则 count += 1
   • 遇到不同元素则 count -= 1
3. 最终留下的候选即为多数元素

动画演示：

[2, 2, 1, 1, 1, 2, 2] 初始状态：candidate=null, count=0↑candidate=2, count=1[2, 2, 1, 1, 1, 2, 2] ↑candidate=2, count=2[2, 2, 1, 1, 1, 2, 2] ↑candidate=2, count=1 // 抵消[2, 2, 1, 1, 1, 2, 2] ↑candidate=1, count=1 // 重置候选[2, 2, 1, 1, 1, 2, 2] ↑candidate=1, count=2[2, 2, 1, 1, 1, 2, 2]  ↑candidate=1, count=1 // 抵消[2, 2, 1, 1, 1, 2, 2]  ↑candidate=2, count=1 // 重置候选

数学证明：为什么这个算法有效？

设真实多数元素为 M，出现频率 > n/2

1. 最坏情况：所有非M元素都与M元素配对抵消
2. 剩余元素：由于 M 的数量 > n/2，即使所有其他元素都与 M 配对抵消，剩余的 M 数量至少为：

   count(M) - (n - count(M)) > n/2 - (n - n/2) = 0

3. 结论：最终留下的候选必定是 M

代码实现（Python）

def majorityElement(nums): candidate = None count = 0 for num in nums: if count == 0: candidate = num # 选择新候选 # 更新计数器：相同+1，不同-1 count += 1 if num == candidate else -1 return candidate

复杂度分析

指标 哈希表法 排序法 摩尔投票法 时间复杂度 O(n) O(n logn) O(n) 空间复杂度 O(n) O(1) O(1) 数据流支持 ❌ ❌ ✅

实际应用场景

1. 实时数据流处理：处理持续输入的传感器数据
2. 大规模日志分析：在内存受限环境下找出高频错误
3. 网络流量监控：识别DDoS攻击源IP
4. 基因组学：寻找优势基因序列

扩展：泛化摩尔投票法（LeetCode 229）

当需要找出出现次数 > n/k 的所有元素时：

def majorityElementK(nums, k): counters = {} # 第一轮：候选筛选 for num in nums: if num in counters: counters[num] += 1 elif len(counters) < k-1: counters[num] = 1 else: # 所有计数器减1 for key in list(counters.keys()): counters[key] -= 1 if counters[key] == 0:  del counters[key] # 第二轮：精确验证 result = [] for candidate in counters: if nums.count(candidate) > len(nums)//k: result.append(candidate) return result

摩尔投票法的局限性

1. 必须存在多数元素：若无满足条件的元素，需二次验证

   # 验证步骤count = 0for num in nums: if num == candidate: count += 1return candidate if count > len(nums)//2 else None

2. 严格频率要求：仅适用于频率 > n/2 的场景

3. 并行化困难：状态依赖特性使其难以分布式处理

替代方案对比

方法 适用场景 空间复杂度 是否在线 摩尔投票法 存在绝对多数元素 O(1) ✅ 随机抽样 允许概率误差 O(1) ❌ 分治法 大数据分布式处理 O(log n) ❌ Count-Min Sketch 频率估计（允许误差） O(k) ✅

总结

摩尔投票法以优雅的数学思想和极致的空间效率，完美解决了绝对众数的识别问题：

1. 核心价值：空间复杂度O(1)，时间复杂度O(n)
2. 适用条件：存在出现频率 > n/2 的元素
3. 工程意义：处理海量数据流的首选算法
4. 扩展应用：可泛化到 n/k 场景（需配合二次验证）

经典思考题：如何用摩尔投票法找出数组中出现频率最高的前k个元素？（提示：结合最小堆）

附录：

• Boyer-Moore原始论文
• LeetCode 229 扩展题解
• 分布式摩尔投票算法研究