169. 多数元素#
大家好！今天我们要聊一个简单却实用的问题——多数元素(Majority Element)。这个问题不仅在算法竞赛中常见，在实际应用中也有着广泛的用途，比如选举系统、数据挖掘和容错计算等。让我们一起探索这个问题的多种解法！
🌟 多数元素：民主选举中的赢家#
什么是”多数元素”？简单来说，就是在一个数组中出现次数超过半数（n/2）的元素。它像是一场选举中获得多数票的候选人，无论其他候选人如何分割选票，这个赢家总是稳操胜券。
问题描述#
题目目标#
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n / 2⌋ 的元素。
示例 1#
输入： nums = [2,2,1,1,1,2,2]
输出： 2
说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。
🎯 问题描述：寻找数组中的主导者#
给定一个大小为n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
例如：
输入: [3,2,3]
输出: 3
输入: [2,2,1,1,1,2,2]
输出: 2🚶♀️ 解法一：计数法（直观但不是最优）#
最简单的方法就是用一个哈希表记录每个元素出现的次数，然后找出出现次数最多的元素：
class Solution {
public int majorityElement(int[] nums) {
// 创建哈希表：key 是数组元素，value 是出现次数
Map<Integer, Integer> counts = new HashMap<>();
// 第 1 步：遍历数组，统计每个数字出现的次数
for (int num : nums) {
// 先取出 num 的历史次数（默认 0），再 +1 写回哈希表
counts.put(num, counts.getOrDefault(num, 0) + 1);
}
// 第 2 步：在哈希表中找出现次数最多的数字
// majority 保存当前出现次数最多的数字
int majority = 0;
// maxCount 保存当前最大出现次数
int maxCount = 0;
// 遍历每个“数字-次数”键值对
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
// 如果当前数字出现次数更大，就更新答案
if (entry.getValue() > maxCount) {
// 更新最大次数
maxCount = entry.getValue();
// 更新对应数字
majority = entry.getKey();
}
}
// 返回出现次数最多的数字（题目保证它就是多数元素）
return majority;
}
}时间复杂度：O(n)，需要遍历数组一次
空间复杂度：O(n)，哈希表最多存储n个键值对
🏇 解法二：排序后取中间值（优雅但非线性时间）#
一个有趣的洞察：如果将数组排序，那么多数元素一定会出现在数组的中间位置！
class Solution {
public int majorityElement(int[] nums) {
// 先对数组升序排序
Arrays.sort(nums);
// 多数元素出现次数 > n/2，排序后一定占据中间位置
return nums[nums.length / 2];
}
}时间复杂度：O(n log n)，排序的时间复杂度
空间复杂度：O(1) 或 O(n)，取决于排序算法的实现
这个解法虽然简洁优雅，但由于排序的时间复杂度是O(n log n)，不是最优的。
🏆 解法三：摩尔投票法（最优解）#
摩尔投票法是解决这个问题的最佳方法，它利用的是多数元素的特性：出现次数超过一半。
基本思路：将第一个数视为候选多数元素，初始计数为1。遍历数组，如果遇到相同的数，计数加1；如果遇到不同的数，计数减1。当计数变为0时，更换候选多数元素。
class Solution {
public int majorityElement(int[] nums) {
// count 表示“当前候选人”的净支持票数
int count = 0;
// candidate 表示当前候选多数元素
Integer candidate = null;
// 遍历每个元素进行“投票”
for (int num : nums) {
// 当票数归零时，重新选择当前元素作为候选人
if (count == 0) {
candidate = num;
}
// 若当前元素等于候选人，票数 +1；否则票数 -1（相互抵消）
count += (num == candidate) ? 1 : -1;
}
// 题目保证一定存在多数元素，因此最终候选人就是答案
return candidate;
}
}时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(1)，只使用了常数额外空间
🎭 摩尔投票法的直观理解：士兵对决#
想象一下，数组中的每个元素都是一名士兵，不同的元素代表不同的队伍。摩尔投票法的过程就像是不同队伍的士兵两两对决，每次对决后双方都阵亡一名。
由于多数元素的士兵数量超过总人数的一半，所以无论如何安排对决，最后一定会有多数元素的士兵存活下来！
🎬 图解摩尔投票法#
以输入数组 [2,2,1,1,1,2,2] 为例：
- 候选人 = 2，计数 = 1
- 遇到2，计数 = 2
- 遇到1，计数 = 1
- 遇到1，计数 = 0，需要重新选举
- 遇到1，候选人 = 1，计数 = 1
- 遇到2，计数 = 0，需要重新选举
- 遇到2，候选人 = 2，计数 = 1
最终候选人是2，恰好是多数元素。
🔍 为什么摩尔投票法有效？#
摩尔投票法的核心思想是”消除”。每当我们遇到一对不同的元素，我们就将它们”消除”。由于多数元素的数量超过n/2，所以：
- 如果我们消除了一对不同的元素（一个多数，一个非多数），数组中剩余的多数元素仍然是多数。
- 即使最坏情况下，所有的非多数元素都与多数元素配对消除，最后剩下的仍然是多数元素。
这就保证了算法的正确性。
🌱 扩展思考：如果不保证存在多数元素？#
如果题目不保证存在多数元素，我们需要在找到候选人后再验证一次：
class Solution {
public int majorityElement(int[] nums) {
// 第 1 阶段：先用摩尔投票法找到候选多数元素
// count 表示当前候选人的净票数
int count = 0;
// candidate 表示当前候选人
Integer candidate = null;
// 遍历数组，进行“加票/减票”抵消
for (int num : nums) {
// 当净票数为 0，说明之前候选人被完全抵消，改推当前数字
if (count == 0) {
candidate = num;
}
// 当前数字支持候选人则 +1，否则 -1
count += (num == candidate) ? 1 : -1;
}
// 第 2 阶段：重新计数，验证候选人是否真的超过一半
count = 0;
// 再遍历一次数组，统计 candidate 实际出现次数
for (int num : nums) {
// 若当前元素等于候选人，则计数 +1
if (num == candidate) {
count++;
}
}
// 边界处理：只有出现次数 > n/2 才是多数元素，否则返回 -1
return count > nums.length / 2 ? candidate : -1; // 如果不存在多数元素，返回-1
}
}🌐 实际应用：从投票系统到故障检测#
多数元素的概念在现实中有广泛应用：
- 分布式系统：使用多数投票确保系统一致性
- 容错计算：利用冗余和多数表决提高系统可靠性
- 图像处理：噪声消除中的多数滤波器
- 数据挖掘：识别数据集中的主要趋势
💯 解题心得：从复杂到简单的思维转变#
解决多数元素问题的过程展示了算法设计中的一个重要思路：从问题的特性出发，寻找最简洁的解法。
- 哈希表解法是最通用的，但需要额外空间
- 排序解法洞察了多数元素的位置特性，但时间复杂度较高
- 摩尔投票法则充分利用了多数元素的数量特性，达到了时间和空间的双重最优
这种从复杂到简单的思维转变是算法设计和优化的精髓所在。
🎓 面试小贴士#
面试中，如果遇到多数元素问题，建议按照以下步骤回答：
- 先提出哈希表计数的方法，这是最直观的
- 然后提出排序后取中间值的方法，展示你能从不同角度思考问题
- 最后介绍摩尔投票法，说明你了解针对特定问题的最优算法
- 别忘了讨论如果不保证存在多数元素的情况，这展示了你的全面思考
🤔 思考题#
如果要求找出数组中所有出现次数超过⌊n/3⌋的元素（最多有2个这样的元素），如何修改摩尔投票法来解决这个问题？
多数元素问题是一个看似简单却蕴含丰富思想的问题。它从简单的计数到巧妙的投票算法，展示了算法设计的不同层次和思维方式。希望通过这个问题，你不仅学会了具体的解法，更领悟到了算法设计的美妙之处！
💪 练习建议#
想要真正掌握这个问题，不妨试试这些练习：
- 尝试手动模拟摩尔投票法的过程，加深理解
- 实现查找数组中出现次数超过n/3的元素
- 思考如何处理数据流中的多数元素问题（即元素是一个一个到达的）
记住，算法学习不是记忆解法，而是理解思路和方法。当你能够自然地推导出摩尔投票法，你就真正掌握了这个问题的精髓！