力扣169：多数元素-抵消法和哈希表-洪萨配资

题目描述

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

方法一：摩尔投票法（最优解）

核心思想

这个算法基于一个关键的抵消思想：由于多数元素的数量超过总数的一半，那么多数元素与其他元素一一抵消后，最后剩下的必然是多数元素。

算法步骤

初始化候选元素candidate和计数器count为 0
遍历数组中的每个元素：
- 如果count为 0，将当前元素设为候选元素
- 如果当前元素等于候选元素，count加 1
- 如果当前元素不等于候选元素，count减 1
遍历结束后，候选元素就是多数元素

代码实现

class Solution { public int majorityElement(int[] nums) { int ans = 0; // 存储当前候选的多数元素 int hp = 0; // 计数器，表示当前候选元素的"生命值" for (int x : nums) { if (hp == 0) { // 生命值为0，需要新的候选 ans = x; // 设置x为新的候选元素 hp = 1; // 初始生命值为1 } else { // 已经有候选元素 if (ans == x) { // 如果当前元素和候选相同 hp += 1; // 生命值+1（支持者增加） } else { // 如果当前元素和候选不同 hp -= 1; // 生命值-1（相互抵消） } } } return ans; // 最终剩下的候选就是多数元素 } }

//简化 class Solution { public int majorityElement(int[] nums) { int ans = 0; int hp = 0; for (int num : nums) { if (hp == 0) { ans = num; } count += (num == ans) ? 1 : -1; } return ans; } }

复杂度分析

时间复杂度：O(n)，只需遍历一次数组
空间复杂度：O(1)，只使用了常数级别的额外空间

算法优势

这是解决多数元素问题的最优算法，特别适合空间要求严格的场景。它巧妙地将问题转化为"擂台比武"，每个元素要么支持当前候选（同门师兄弟），要么反对（敌人），最终多数元素会胜出。

方法二：哈希表法（最直观）

核心思想

使用哈希表记录每个元素出现的次数，然后找到出现次数超过一半的元素。这是最直观的解法，也是面试中最容易想到的方法。

算法步骤

创建一个哈希表来记录每个数字出现的次数
遍历数组，更新哈希表中每个数字的计数
遍历哈希表，找到出现次数超过 n/2 的元素

代码实现

class Solution { public int majorityElement(int[] nums) { // 创建哈希表 Map<Integer, Integer> countMap = new HashMap<>(); // 统计每个数字出现的次数 for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1); // 可以在统计过程中直接判断，提高效率 if (countMap.get(num) > nums.length / 2) { return num; } } // 理论上不会执行到这里 return -1; } }

简化版本

class Solution { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int maxCount = 0; int result = 0; for (int num : nums) { int count = map.getOrDefault(num, 0) + 1; map.put(num, count); // 在遍历过程中更新最大值 if (count > maxCount) { maxCount = count; result = num; } } return result; } }

复杂度分析

时间复杂度：O(n)，需要遍历一次数组，哈希表操作平均O(1)
空间复杂度：O(k)，其中k是数组中不同元素的数量，最坏情况下为O(n)

方法对比与选择建议

特性	Boyer-Moore算法	哈希表统计法
时间复杂度	O(n)	O(n)
空间复杂度	O(1)	O(n)
实现难度	中等（需要理解算法原理）	简单（直观易懂）
是否需要验证	需要（如果不确定存在多数元素）	不需要（遍历时即可判断）
实际性能	更快（常数时间小）	稍慢（哈希表操作有开销）
适用场景	空间限制严格时	代码可读性优先时

选择建议

面试场景：先讲解Boyer-Moore算法，展示算法优化思想
实际工作：如果对空间要求不高，使用哈希表法更稳妥
比赛/刷题：追求极致性能用Boyer-Moore，追求快速实现用哈希表

常见变种问题

1. 寻找出现次数超过 n/3 的元素

class Solution { public List<Integer> majorityElement(int[] nums) { // 最多有两个这样的元素 List<Integer> result = new ArrayList<>(); // 使用Boyer-Moore算法的扩展版本 int candidate1 = 0, candidate2 = 0; int count1 = 0, count2 = 0; for (int num : nums) { if (num == candidate1) { count1++; } else if (num == candidate2) { count2++; } else if (count1 == 0) { candidate1 = num; count1 = 1; } else if (count2 == 0) { candidate2 = num; count2 = 1; } else { count1--; count2--; } } // 验证候选元素是否真的超过n/3 count1 = 0; count2 = 0; for (int num : nums) { if (num == candidate1) count1++; else if (num == candidate2) count2++; } if (count1 > nums.length / 3) result.add(candidate1); if (count2 > nums.length / 3) result.add(candidate2); return result; } }

2. 寻找出现次数最多的元素（众数）

class Solution { public int majorityElement(int[] nums) { // 使用哈希表统计频率 Map<Integer, Integer> countMap = new HashMap<>(); int maxCount = 0; int result = nums[0]; for (int num : nums) { int count = countMap.getOrDefault(num, 0) + 1; countMap.put(num, count); if (count > maxCount) { maxCount = count; result = num; } } return result; } }