Hot 100 --- 多数元素

本文概览：本文讲解多数元素：多数元素出现次数超过 n/2，所以排序后下标 n/2 的位置一定是它；更优的摩尔投票法把问题看成"两两抵消"，因为多数元素的总数超过其余元素之和，抵消到最后剩下的就是它，O(n) 时间、O(1) 空间

一、题目

二、题目分析

1. 题目要求

给定一个大小为 n 的数组 nums，返回其中的多数元素。

多数元素是指在数组中出现次数大于 ⌊n / 2⌋ 的元素。可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：nums = [3, 2, 3] → 3

示例 2：nums = [2, 2, 1, 1, 1, 2, 2] → 2

2. 怎么想这题？

题目要找一个出现次数最多的元素，而且它有个很强的保证：次数超过 n/2（一半以上）。

这个"超过一半"是整个题的题眼，围绕它能想出三种层次的解法：

• 老老实实数：用哈希表把每个数出现几次统计出来，谁超过 n/2 就返回谁。直观，但要多花 O(n) 的空间。
• 利用"超过一半"这个位置性质：既然它占了一半以上，把它排好序之后，数组正中间那个位置是不是一定就是它？顺着这个想法能省掉哈希表。
• 再往深想一层：过半意味着它比其他所有元素的总数还多。如果让元素"两两抵消"，它是不是注定抵消不完、最后剩下来？这就是摩尔投票法，能做到 O(n) 时间、O(1) 空间。

3. 需要解决哪几个问题？

问题一：哈希表计数怎么实现？为什么它拿不到"O(1) 空间"？

问题二：为什么排序之后，下标 n/2 的位置一定是多数元素？怎么证明？

问题三（核心）：摩尔投票法里那个"抵消"到底在干什么？为什么多数元素抵消到最后一定剩得下？

三、方法一：哈希表计数，O(n) 空间

1. 思路概览

public int majorityElement(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
int n = nums.length;
for (int num : nums) {
int c = count.getOrDefault(num, 0) + 1;
count.put(num, c);
if (c > n / 2) {
return num; // 已经超过一半，可以直接返回
}
}
return –1;
}

思路简要说明：

2. 思路详解

count.getOrDefault(num, 0) 的意思是"取出 num 当前的计数，如果没有就当 0"，加 1 之后再写回 map。每写回一次就判断一下有没有过半。

以 [2, 2, 1, 1, 1, 2, 2]（n = 7，一半是 3）为例：

num=2：计数 2→1
num=2：计数 2→2
num=1：计数 1→1
num=1：计数 1→2
num=1：计数 1→3
num=2：计数 2→3
num=2：计数 2→4 > 3 → 返回 2 ✓

思路没有绕弯，唯一的问题是那个哈希表——最坏情况下要存下所有不同的数，空间是 O(n)。题目没强制要求省空间，但既然"超过一半"这个条件还能利用，就值得往下想。

3. 复杂度分析

时间复杂度 O(n)：遍历一次，哈希操作均摊 O(1)。

空间复杂度 O(n)：哈希表最多存 n 个不同的键。

四、方法二：排序后取中间，O(n log n)

1. 思路概览

public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}

思路简要说明：

2. 思路详解

为什么中间那个位置一定是多数元素？

设多数元素为 m，它出现了 c 次，题目保证 c > n / 2，也就是 c ≥ ⌊n/2⌋ + 1。

排好序之后，所有等于 m 的元素会连成一整块，占据一段连续的位置。用反证法：假设下标 n/2 那个位置上不是 m，那说明 m 那一整块要么整个在它左边、要么整个在它右边。

• 如果整块都在下标 n/2 的左边，那它最多只能占据前 ⌊n/2⌋ 个位置，也就是 c ≤ ⌊n/2⌋，和 c ≥ ⌊n/2⌋ + 1 矛盾；
• 如果整块都在右边，同理最多也只能占 ⌊n/2⌋ 个位置，同样矛盾。

两边都不可能，所以下标 n/2 上只能是 m。

拿 [2, 2, 1, 1, 1, 2, 2] 看，排序后是 [1, 1, 1, 2, 2, 2, 2]，n = 7，n / 2 = 3，下标 3 上正好是 2 ✓。

这个方法的巧妙之处在于：它压根不用知道每个数出现几次，只靠"过半 ⇒ 必然霸占中间位置"这一条性质就够。代价是排序要 O(n log n)，比线性慢。

3. 复杂度分析

时间复杂度 O(n log n)：排序占主要开销。

空间复杂度 O(1)：只用了下标。

五、方法三：摩尔投票法，O(n) 时间 + O(1) 空间

1. 思路概览

public int majorityElement(int[] nums) {
int candidate = nums[0];
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num; // 前面的都被抵消光了，换这个数当候选人
count = 1;
} else if (num == candidate) {
count++; // 支持票 +1
} else {
count—; // 反对票，抵消掉一张支持票
}
}
return candidate;
}

思路简要说明：

2. 思路详解

第一步：把问题看成"互相抵消"

多数元素出现次数超过 n/2，也就是说：它的个数，比其余所有元素加起来还多。

这句话很容易被忽略，但它是整个方法的根基。既然它一方人马比"其他所有人加起来"还多，那就让不同阵营的元素两两抵消——每抵消掉一个多数元素，也必然要搭上一个别的元素。就算把其他元素全部拿去和它拼掉，它也还剩得下（因为它的总数本来就更多）。所以抵消到最后，场上剩下的只能是它。

第二步：candidate 和 count 在记录什么

代码把上面这个过程压缩成了两个变量：

• candidate：当前占上风的那个元素；
• count：它手里还剩多少"净票"（支持它的数量减去被反对掉的）。

遍历时的三种动作：

• 遇到和 candidate 相同的数 → 是自己人，count++；
• 遇到和 candidate 不同的数 → 换掉一个，count–（一票支持被一票反对抵消）；
• count 减到 0 → 说明前面攒的票全被抵消光了，candidate 已经名存实亡。这时让当前这个数当新候选人，count = 1 重新开始。

为什么归零时可以放心换人？ 因为 count 归零意味着"从开头到现在这一段，支持票和反对票正好打成平手，整段全抵消了"。这一段既然能自我消化干净，把它整个丢掉也不影响剩下的部分——后面那些数的"谁更多"的格局，和前面这一段的抵消结果无关。所以可以放心从那一位重新开始数。

第三步：完整执行过程

以 [2, 2, 1, 1, 1, 2, 2]（答案是 2）为例：

num=2：count=0 → candidate=2, count=1 ← 2 上台
num=2：== candidate → count=2 ← 又来一个自己人
num=1：!= candidate → count=1 ← 1 抵消掉一张票
num=1：!= candidate → count=0 ← 又抵消一张，2 被拼光了
num=1：count=0 → candidate=1, count=1 ← 1 上台
num=2：!= candidate → count=0 ← 2 把 1 拼光
num=2：count=0 → candidate=2, count=1 ← 2 再次上台
返回 candidate = 2 ✓

再看示例 1 的 [3, 2, 3]：

num=3：count=0 → candidate=3, count=1
num=2：!= → count=0
num=3：count=0 → candidate=3, count=1
返回 3 ✓

可以留意到：中间 candidate 换成过 1，也归零过好几次，但最后站着的还是 2——因为多数元素总数最多，抵消到最后剩下的一定是它。中间那些起伏只是"还没分出胜负"的临时状态。

第四步：代码细节

• count == 0 时统一处理：这个分支同时兼顾了"数组第一个元素"（初始 count = 0，第一个数自然上台）和"候选人被拼光后换人"，不用给第一个元素单独写逻辑。
• 最后不需要再验证：题目保证多数元素一定存在，所以循环结束时 candidate 必然是答案。如果题目不保证，就得再扫一遍数组确认它真的过半。
• count 的含义要记准：它不是"候选人出现的总次数"，而是"净票数"，中途被抵消掉的票已经从里面扣掉了。

3. 复杂度分析

时间复杂度 O(n)：一次遍历，每个元素常数次比较。

空间复杂度 O(1)：只有 candidate 和 count 两个变量。

六、总结

三种方法一层比一层省，共同的基础都是题目那句"出现次数大于 ⌊n/2⌋"：

• 老老实实计数，是把"过半"交给哈希表去判断；
• 排序取中间，是把"过半"翻译成"位置性质"——它必然霸占正中间；
• 摩尔投票，是把"过半"翻译成"数量对比"——它比其余所有元素加起来还多，所以两两抵消之后它一定还在。

面试里最常被追问的是摩尔投票法，重点不在代码（就那么几行），而在于能不能说清"为什么抵消到最后剩下的就是多数元素"这一点。