面试必看：多数元素 II（摩尔投票法实战）

学习笔记：LeetCode 229. 多数元素 II（摩尔投票法实战）

题目描述

给定一个大小为n nn的整数数组，找出数组中所有出现次数超过⌊ n / 3 ⌋ \lfloor n/3 \rfloor⌊n/3⌋的元素。
进阶约束：要求算法时间复杂度为O ( n ) O(n)O(n)，空间复杂度为O ( 1 ) O(1)O(1)。

示例

• 输入：nums = [3,2,3]，输出：[3]
• 输入：nums = [1]，输出：[1]
• 输入：nums = [1,2]，输出：[1,2]

核心特征分析

结合题目要求与数学性质，提炼问题核心特征：

1. 固定比例众数查找：目标为寻找出现次数超过n / k n/kn/k（本题k = 3 k=3k=3）的元素，是众数问题的经典变种；
2. 数学边界约束：通过反证法可推导，满足条件的元素数量不超过k − 1 k-1k−1个（本题最多存在2个符合条件的元素）。若存在3个元素均满足次数要求，总出现次数会超过数组长度n nn，与定义矛盾；
3. 严苛空间限制：O ( 1 ) O(1)O(1)空间复杂度是解题难点，直接排除哈希表、排序等依赖额外存储空间的常规解法，O ( n ) O(n)O(n)时间的基础解法易实现，但无法满足进阶优化要求。

算法选型：摩尔投票法

选型依据

1. 匹配数学约束：基于本题最多2个目标元素的特性，仅需维护两个候选值+两个计数器，符合常数级空间的要求；
2. 满足复杂度指标：仅需常数次线性遍历数组，实现O ( n ) O(n)O(n)时间复杂度 +O ( 1 ) O(1)O(1)空间复杂度，完美契合题目进阶约束；
3. 贪心策略核心：算法通过局部抵消不同元素的计数，保留出现频次更高的候选元素，以局部最优推导全局最优，是贪心思想的典型落地。

算法适配性对比

解法方案	时间复杂度	空间复杂度	弃选原因
哈希表统计	O ( n ) O(n)O(n)	O ( n ) O(n)O(n)	无法满足O ( 1 ) O(1)O(1)空间约束
排序遍历	O ( n log ⁡ n ) O(n\log n)O(nlogn)	O ( log ⁡ n ) O(\log n)O(logn)	排序带来非线性时间开销，效率更低
暴力枚举	O ( n 2 ) O(n^2)O(n2)	O ( 1 ) O(1)O(1)	时间复杂度过高，无法通过大数据量测试

解题模式识别

本题属于固定比例众数查找题型，是摩尔投票法的标准应用场景，具备明确的题型模板：

1. 基础模板：寻找出现次数超过n / 2 n/2n/2的元素（维护1个候选值）；
2. 本题模板：寻找出现次数超过n / 3 n/3n/3的元素（维护2个候选值）；
3. 通用拓展模板：寻找出现次数超过n / k n/kn/k的元素（维护k − 1 k-1k−1个候选值）。

触发信号：题目出现「固定比例众数+线性时间+常数空间」组合约束时，优先选择摩尔投票法。

解题思路

摩尔投票法分为投票筛选候选和验证候选有效性两个核心阶段，缺一不可：

阶段1：投票筛选候选

初始化两个候选值candidate1/candidate2、两个计数器count1/count2，初始计数器置为0。
遍历数组中的每个元素num，执行以下逻辑：

1. 若当前元素等于candidate1，对应计数器count1++；
2. 否则若当前元素等于candidate2，对应计数器count2++；
3. 否则若count1 == 0，将当前元素赋值给candidate1，并重置count1 = 1；
4. 否则若count2 == 0，将当前元素赋值给candidate2，并重置count2 = 1；
5. 其余情况，两个计数器同时自减（不同元素相互抵消）。

阶段2：验证候选有效性

投票阶段仅能筛选出潜在候选，无法保证一定满足次数要求，因此需要二次遍历数组，统计两个候选值的真实出现次数，筛选出次数严格大于n / 3 n/3n/3的元素作为最终结果。

完整解题代码（C++）

#include<vector>usingnamespacestd;classSolution{public:vector<int>majorityElement(vector<int>&nums){intn=nums.size();// 初始化候选值与计数器intcandidate1=0,candidate2=0;intcount1=0,count2=0;// 第一步：摩尔投票，筛选潜在候选元素for(inti=0;i<n;++i){intnum=nums[i];if(candidate1==num){count1++;}elseif(candidate2==num){count2++;}elseif(count1==0){// 替换空候选位candidate1=num;count1=1;}elseif(count2==0){// 替换空候选位candidate2=num;count2=1;}else{// 不同元素相互抵消计数count1--;count2--;}}// 重置计数器，统计候选值真实出现次数count1=0,count2=0;for(inti=0;i<n;++i){intnum=nums[i];if(candidate1==num)count1++;elseif(candidate2==num)count2++;}vector<int>ans;// 独立判断，支持同时存入两个有效结果if(count1>n/3)ans.push_back(candidate1);if(count2>n/3)ans.push_back(candidate2);returnans;}};

代码说明

1. 变量定义：仅使用固定数量的整型变量，满足O ( 1 ) O(1)O(1)空间要求；
2. 投票逻辑：严格遵循抵消规则，筛选出最多2个潜在候选；
3. 验证逻辑：二次遍历保证结果正确性，避免投票阶段的无效候选；
4. 结果收集：使用两个独立if判断，支持同时返回两个符合条件的元素。

复杂度分析

时间复杂度

算法对数组进行两次线性遍历，单次遍历时间开销为O ( n ) O(n)O(n)，总时间复杂度为O ( n ) \boldsymbol{O(n)}O(n)，n nn为数组长度。

空间复杂度

仅使用常数个局部变量，无随输入规模增长的额外存储空间，结果集不计入算法空间复杂度统计，总空间复杂度为O ( 1 ) \boldsymbol{O(1)}O(1)。

关键注意事项

1. 必须执行验证步骤：投票阶段的抵消机制可能产生无效候选，二次遍历验证是保证结果正确的核心；
2. 独立判断结果：满足条件的元素最多有2个，禁止使用else if，否则会丢失第二个有效结果；
3. 通用拓展性：该思路可直接迁移至寻找超过n / k n/kn/k次元素的场景，仅需调整候选值与计数器的数量。