扩展摩尔投票法：找出出现次数超过 n/3 的元素

标签：LeetCode 169, 摩尔投票法, 多数元素, 算法扩展, 数组处理

在解决多数元素问题时，我们学习了经典的摩尔投票法处理出现次数超过 n/2 的情况。那么，当问题扩展为找出出现次数超过 n/3 的元素时，该如何解决呢？本文将深入探讨摩尔投票法的扩展应用。

问题描述

给定一个大小为 n 的整数数组，找出所有出现次数 大于 ⌊n/3⌋ 的元素。要求时间复杂度 O(n)，空间复杂度 O(1)。

示例：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]
解释：1 和 2 都出现 3 次，大于 ⌊8/3⌋ = 2

关键洞察

1. 数学约束：出现次数超过 n/3 的元素最多有 2 个

   • 如果 3 个元素都超过 n/3，总次数将超过 n，不可能

2. 扩展思路：使用两个候选元素和两个计数器

   • 维护两个候选元素 candidate1, candidate2
   • 维护对应的计数器 count1, count2
   • 使用抵消策略处理其他元素

算法原理

1. 初始化：两个候选元素设为特殊值（如 null），计数器设为 0
2. 投票阶段：
   • 当前元素等于任一候选元素 → 对应计数器加 1
   • 当任一计数器为 0 → 将当前元素设为新候选
   • 当前元素不等于任一候选 → 两个计数器都减 1（抵消）
3. 验证阶段：检查候选元素是否真正超过 n/3

Java 实现

import java.util.*;class Solution {public List<Integer> majorityElement(int[] nums) {// 初始化候选元素和计数器Integer candidate1 = null;Integer candidate2 = null;int count1 = 0;int count2 = 0;// 第一轮遍历：投票过程for (int num : nums) {if (candidate1 != null && num == candidate1) {count1++;} else if (candidate2 != null && num == candidate2) {count2++;} else if (count1 == 0) {candidate1 = num;count1 = 1;} else if (count2 == 0) {candidate2 = num;count2 = 1;} else {// 抵消操作count1--;count2--;}}// 第二轮遍历：验证候选元素List<Integer> result = new ArrayList<>();count1 = 0;count2 = 0;for (int num : nums) {if (candidate1 != null && num == candidate1) count1++;if (candidate2 != null && num == candidate2) count2++;}int n = nums.length;if (count1 > n/3) result.add(candidate1);if (count2 > n/3) result.add(candidate2);return result;}
}

算法演示

以数组 [1,2,3,2,1,2,3,1,2] 为例（n=9，需要出现次数 > 3）

投票阶段

元素	candidate1	count1	candidate2	count2	操作说明
1	1	1	null	0	初始化 candidate1
2	1	1	2	1	初始化 candidate2
3	1	0	2	0	抵消 (1-1, 2-1)
2	1	0	2	1	count1=0, 使用candidate2
1	1	1	2	1	重置 candidate1
2	1	1	2	2	增加 candidate2
3	1	0	2	1	抵消
1	1	1	2	1	重置 candidate1
2	1	1	2	2	增加 candidate2

验证阶段

• candidate1 = 1 → 出现次数：4 > 3
• candidate2 = 2 → 出现次数：4 > 3
• 结果：[1, 2]

复杂度分析

• 时间复杂度：O(2n) = O(n)，两次线性遍历
• 空间复杂度：O(1)，仅使用常数空间（两个候选元素和两个计数器）

算法关键点

1. 候选元素初始化：使用包装类型 Integer 以便处理 null 值
2. 条件判断顺序：优先检查是否匹配候选元素，再检查计数器是否为0
3. 抵消策略：当元素与两个候选元素都不同时，同时减少两个计数器
4. 验证必要性：投票结果需要验证，因为：
   • 计数器可能被其他元素干扰
   • 数组可能没有满足条件的元素

通用化公式

摩尔投票法可进一步扩展为寻找出现次数超过 n/k 的元素：

1. 最多有 k-1 个候选元素
2. 维护 k-1 个候选元素和计数器
3. 投票阶段：
   • 匹配候选 → 对应计数器加1
   • 计数器为0 → 设为新候选
   • 都不匹配 → 所有计数器减1
4. 验证候选元素的实际出现次数

实际应用场景

1. 大数据分析：从海量数据中找出高频项
2. 网络流量监控：检测异常高频访问
3. 推荐系统：识别热门内容
4. 日志分析：查找频繁出现的错误类型
5. 选举系统：统计多候选人得票情况

边界情况处理

1. 候选元素为 null 的情况：

   if (candidate1 != null && num == candidate1)
   

2. 数组长度小于3：

   • 当 n < 3 时，⌊n/3⌋ = 0，所有元素都满足条件
   • 但实际需统计出现次数 > 0 的元素（根据定义）

3. 没有满足条件的元素：

   // 验证阶段会过滤掉不满足条件的候选
   if (count1 > n/3) result.add(candidate1);
   

总结

扩展摩尔投票法展示了算法设计的精妙之处：

1. 数学洞察：利用问题约束（最多 k-1 个候选）
2. 空间优化：O(1) 空间解决统计问题
3. 高效性：O(n) 时间复杂度
4. 通用性：可扩展为 n/k 问题

掌握这种扩展思维，能帮助我们在面对各类统计问题时，设计出高效的空间优化算法。摩尔投票法不仅是解决多数元素问题的利器，更是算法设计中"以空间换时间"思想的经典体现。

思考挑战：如何扩展该算法处理出现次数超过 n/4 的情况？欢迎在评论区分享你的解决方案！