LeetCode 169. 多数元素

题目描述

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

多数元素是指在数组中出现次数 大于 ⌊n / 2⌋ 的元素。

题目已经明确告诉我们：数组一定存在多数元素。

示例分析

示例 1

输入: nums = [3,2,3]
输出: 3

数组长度为 3，3 出现了 2 次，满足 2 > 3 / 2，所以它就是多数元素。

示例 2

输入: nums = [2,2,1,1,1,2,2]
输出: 2

数组长度为 7，2 出现了 4 次，满足 4 > 7 / 2，因此返回 2。

解题思路

这道题最经典的做法就是 摩尔投票法。

你给出的这份代码非常精简：

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}

虽然代码很短，但背后的思想非常巧妙。

什么是摩尔投票法

我们可以把数组中的元素看成在“投票”。

• 如果当前数字和候选人相同，那么候选人的票数加 1

• 如果当前数字和候选人不同，那么候选人的票数减 1

当票数减到 0 时，说明当前候选人在前面这一段中已经“抵消完了”，此时我们就更换候选人。

最终剩下来的那个候选人，就是多数元素。

为什么可以抵消

这是这道题最关键的地方。

因为题目保证数组中一定存在一个元素，它的出现次数 大于所有其他元素出现次数之和。

所以即使我们不断让不同元素两两抵消：

• 多数元素和非多数元素抵消一次

• 非多数元素数量会减少

• 多数元素数量也会减少

但由于多数元素本来就比其他所有元素总数还多，所以最后一定还能剩下来。

也就是说，抵消到最后留下的一定是多数元素。

结合代码理解

1. 定义候选人和票数

int x = 0, votes = 0;

• x 表示当前候选人

• votes 表示当前候选人的票数

2. 遍历数组

for (int num : nums){

逐个处理数组中的元素。

3. 如果票数为 0，就更换候选人

if (votes == 0) x = num;

当票数变成 0 时，说明前面的候选人已经和其他数字互相抵消掉了。

这时当前数字就有资格成为新的候选人。

4. 当前数字和候选人相同，票数加 1；否则减 1

votes += num == x ? 1 : -1;

这一步就是摩尔投票法的核心。

• 如果当前元素等于候选人，说明有人支持他，票数加 1

• 如果当前元素不等于候选人，说明有人反对他，票数减 1

5. 最终返回候选人

return x;

因为题目保证多数元素一定存在，所以最后留下来的候选人 x 一定就是答案。

执行过程模拟

我们用这个例子来模拟：

nums = [2,2,1,1,1,2,2]

初始化：

x = 0, votes = 0

第一次遍历到 2

votes == 0，所以把 2 设为候选人：

x = 2

然后当前数字等于候选人，票数加 1：

votes = 1

第二次遍历到 2

当前数字还是 2，和候选人相同：

votes = 2

第三次遍历到 1

当前数字 1 不等于候选人 2：

votes = 1

第四次遍历到 1

继续抵消：

votes = 0

说明前面这部分已经互相抵消完了。

第五次遍历到 1

因为 votes == 0，所以重新选候选人：

x = 1

然后当前数字等于候选人：

votes = 1

第六次遍历到 2

当前数字 2 不等于候选人 1：

votes = 0

又抵消完了。

第七次遍历到 2

票数为 0，重新设置候选人：

x = 2
votes = 1

遍历结束，返回 2。

为什么最后一定是多数元素

我们换一种更直观的理解方式。

假设多数元素是 a，其他元素统称为“非 a”。

因为 a 的数量超过数组长度的一半，所以：

a 的个数 > 非 a 的个数

每次遇到不同元素时，我们都可以理解为：

• 一个 a 和一个非 a 抵消掉

即使这样不断抵消，最后 a 仍然会剩下。

所以最后的候选人一定是多数元素。

这道题为什么不需要哈希表

很多同学第一次做这题时，会先想到用 HashMap 统计每个数字出现的次数。

这种方法当然可以做出来，但需要额外空间。

例如：

1. 遍历数组

2. 用哈希表记录每个元素的出现次数

3. 再找出出现次数大于 n/2 的元素

这种做法的时间复杂度是 O(n)，空间复杂度是 `O(n)“。

而摩尔投票法同样能做到 O(n) 的时间复杂度，但空间复杂度只有 O(1)，显然更优。

复杂度分析

时间复杂度

O(n)

数组只遍历了一次。

空间复杂度

O(1)

只使用了两个变量 x 和 votes。

和哈希表解法对比

哈希表解法

优点：

• 思路直接，容易想到

• 统计出现次数非常清晰

缺点：

• 需要额外 O(n) 空间

摩尔投票法

优点：

• 时间复杂度 O(n)

• 空间复杂度 O(1)

• 代码非常简洁

缺点：

• 思想不太直观，第一次接触不容易理解

所以这道题最推荐掌握的解法就是摩尔投票法。

总结

这道题的核心在于理解 “抵消” 这个思想：

1. 用 x 表示当前候选人

2. 用 votes 表示当前候选票数

3. 相同元素让票数加 1，不同元素让票数减 1

4. 票数减到 0，就更换候选人

5. 最后留下来的候选人一定是多数元素

这类题并不难写，真正难的是第一次理解为什么它一定正确。 只要你把“多数元素数量大于其他所有元素总和，所以抵消之后一定还能剩下”这个点想明白，这题就彻底吃透了。