DeepSeek LeetCode 229. 多数元素 II Java实现

LeetCode 229. 多数元素 II Java 实现思路Boyer-Moore 投票算法扩展版出现次数超过 ⌊n/3⌋ 的元素最多只有 2 个。因此可以用两个候选人和两个计数器在 O(n) 时间内找出可能的候选人再遍历一次验证。算法步骤第一遍遍历维护两个候选 candidate1、candidate2 和对应计数 count1、count2。遇到相同候选人则计数加一否则若某计数为 0则替换候选人否则两个计数都减一。第二遍遍历统计两个候选人的真实出现次数。将出现次数 n/3 的候选人加入结果。Java 代码classSolution{publicListIntegermajorityElement(int[]nums){intcandidate10,candidate20;intcount10,count20;// 第一遍找出两个可能的候选人for(intnum:nums){if(count10numcandidate1){count1;}elseif(count20numcandidate2){count2;}elseif(count10){candidate1num;count11;}elseif(count20){candidate2num;count21;}else{count1--;count2--;}}// 第二遍验证候选人是否真的超过 n/3count10;count20;for(intnum:nums){if(numcandidate1){count1;}elseif(numcandidate2){count2;}}ListIntegerresnewArrayList();intnnums.length;if(count1n/3)res.add(candidate1);if(count2n/3candidate2!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 与真实元素冲突。