LeetCode 229. 多数元素 II Java 实现

思路：Boyer-Moore 投票算法（扩展版）

出现次数超过 ⌊n/3⌋ 的元素最多只有 2 个。
因此可以用两个候选人和两个计数器，在 O(n) 时间内找出可能的候选人，再遍历一次验证。

算法步骤：

1. 第一遍遍历，维护两个候选 candidate1、candidate2 和对应计数 count1、count2。
2. 遇到相同候选人则计数加一；否则若某计数为 0，则替换候选人；否则两个计数都减一。
3. 第二遍遍历，统计两个候选人的真实出现次数。
4. 将出现次数 > n/3 的候选人加入结果。

Java 代码

classSolution{publicList<Integer>majorityElement(int[]nums){intcandidate1=0,candidate2=0;intcount1=0,count2=0;// 第一遍：找出两个可能的候选人for(intnum:nums){if(count1>0&&num==candidate1){count1++;}elseif(count2>0&&num==candidate2){count2++;}elseif(count1==0){candidate1=num;count1=1;}elseif(count2==0){candidate2=num;count2=1;}else{count1--;count2--;}}// 第二遍：验证候选人是否真的超过 n/3count1=0;count2=0;for(intnum:nums){if(num==candidate1){count1++;}elseif(num==candidate2){count2++;}}List<Integer>res=newArrayList<>();intn=nums.length;if(count1>n/3)res.add(candidate1);if(count2>n/3&&candidate2!=candidate1)res.add(candidate2);returnres;}}

复杂度分析

· 时间复杂度：O(n)，遍历数组两次。
· 空间复杂度：O(1)，只用了常数个变量。

示例

输入:nums=[3,2,3]输出:[3]输入:nums=[1,1,1,3,3,2,2,2]输出:[1,2]输入:nums=[1,2,3,4]输出:[]

关键点

· 候选人最多两个，因为若某元素出现次数 > n/3，三个这样的元素出现次数之和就超过 n，矛盾。
· 投票阶段只负责筛选出“可能”的候选人，必须进行第二次遍历验证。
· 使用 count > 0 && num == candidate 的判断，可以避免初始值 0 与真实元素冲突。