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

题目描述

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

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

核心思想

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

算法步骤

1. 初始化候选元素candidate和计数器count为 0

2. 遍历数组中的每个元素：

   • 如果count为 0，将当前元素设为候选元素

   • 如果当前元素等于候选元素，count加 1

   • 如果当前元素不等于候选元素，count减 1

3. 遍历结束后，候选元素就是多数元素

代码实现

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)，只使用了常数级别的额外空间

算法优势

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

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

核心思想

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

算法步骤

1. 创建一个哈希表来记录每个数字出现的次数

2. 遍历数组，更新哈希表中每个数字的计数

3. 遍历哈希表，找到出现次数超过 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)

方法对比与选择建议

选择建议

1. 面试场景：先讲解Boyer-Moore算法，展示算法优化思想

2. 实际工作：如果对空间要求不高，使用哈希表法更稳妥

3. 比赛/刷题：追求极致性能用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; } }

总结

多数元素问题是一个经典的算法问题，展示了不同解法之间的权衡：

1. Boyer-Moore投票算法是空间最优解，体现了算法设计的巧妙性

2. 哈希表统计法是最直观的解，易于理解和实现

3. 排序法虽然简单，但时间复杂度较高

4. 分治法展示了递归解决问题的思路

在实际应用中，根据具体需求选择合适的解法。如果空间限制严格，Boyer-Moore算法是最佳选择；如果追求代码可读性和维护性，哈希表法更合适。无论选择哪种方法，理解其背后的原理和适用场景才是最重要的。

刷题建议：掌握Boyer-Moore算法的思想和实现，这在面试中经常被考察。同时也要熟悉哈希表解法，因为它适用于更广泛的统计问题。