【中等】力扣算法题解析LeetCode229：多数元素 II

关注文末推广名片，即可免费获得本题测试源码！

题目来源：LeetCode229：多数元素 II

问题抽象： 设计算法在整数数组中高效找出所有出现次数超过 ⌊n/3⌋ 的元素（n 为数组长度），需满足以下核心需求：

1. 筛选条件：

   • 目标元素出现频次严格大于 ⌊n/3⌋（向下取整）；
   • 结果元素数量最多为 2 个（数学性质：超过 ⌊n/3⌋ 的元素数 ≤2）。

2. 计算约束：

   • 时间复杂度 O(n)（单次或常数次遍历数组）；
   • 空间复杂度 O(1)（仅使用常数个额外变量，禁用哈希表等线性空间结构）；
   • 核心策略：摩尔投票法扩展（维护两个候选元素及其计数器）。

3. 算法流程：

   • 第一轮遍历（投票）：
     • 初始化两个候选者 cand1, cand2 及其计数器 cnt1=0, cnt2=0；
     • 遍历数组，根据当前元素匹配情况更新计数器或替换候选者（抵消逻辑）；
   • 第二轮遍历（验证）：
     • 统计 cand1 和 cand2 的实际出现次数；
     • 仅保留频次 > ⌊n/3⌋ 的元素。

4. 边界处理：

   • 空数组返回空列表；
   • 数组长度 n=1 时，唯一元素即为结果；
   • 多个元素满足条件时需全部输出（如 [1,1,2,2,3] 中 n=5，⌊5/3⌋=1，1 和 2 均需输出）；
   • 无满足条件元素时返回空列表。

输入：整数数组 nums（长度 n ∈ [0,5×10^4]，元素值 ∈ [-10^9,10^9]）
输出：整数列表（所有满足条件的元素，顺序不限）

解题思路

使用 摩尔投票法 的扩展版本，核心思想是通过抵消操作来找出可能满足条件的候选元素。由于出现次数超过 ⌊ n/3 ⌋ 的元素最多有两个，因此维护两个候选元素 candidate1 和 candidate2，并记录它们的出现计数 count1 和 count2。算法分为两个阶段：

1. 投票阶段：遍历数组，更新候选元素和计数：

   • 若当前元素等于任一候选元素，对应计数加1。
   • 若当前元素与候选元素均不同：
     • 若任一计数为0，则替换对应的候选元素并重置计数为1。
     • 若两个计数均不为0，则两个计数均减1（抵消操作）。

2. 验证阶段：再次遍历数组，统计两个候选元素的实际出现次数。若实际次数超过 ⌊ n/3 ⌋，则将其加入结果列表。

代码实现（Java版）🔥点击下载源码

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--; } } // 重置计数，用于验证阶段 count1 = 0; count2 = 0; // 第二次遍历：验证阶段，统计候选元素实际出现次数 for (int num : nums) { if (candidate1 != null && num == candidate1) count1++; if (candidate2 != null && num == candidate2) count2++; } // 生成结果列表 List<Integer> result = new ArrayList<>(); int n = nums.length; if (count1 > n / 3) result.add(candidate1); if (count2 > n / 3) result.add(candidate2); return result; }}

代码说明

1. 初始化：使用 Integer 类型（可为 null）存储候选元素，避免与数组中的值冲突。
2. 投票阶段：
   • 遍历数组，根据当前元素更新候选元素或进行抵消操作。
   • 当遇到与候选元素相同的元素时，对应计数加1。
   • 当遇到新元素且计数为0时，替换候选元素。
   • 当遇到新元素且计数均不为0时，两个计数减1（抵消三个不同元素）。
3. 验证阶段：
   • 重置计数后重新遍历数组，统计候选元素的实际出现次数。
   • 若实际次数超过 ⌊ n/3 ⌋，则加入结果列表。
4. 结果返回：返回包含所有满足条件元素的列表。

提交详情（执行用时、内存消耗）