多数元素

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

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• 输入保证数组中一定有一个多数元素

进阶： 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

解法一（哈希计数）：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> cnt;
        int n = nums.size();

        for (int num : nums)
        {
            cnt[num]++;
            if (cnt[num] > n / 2)
            {
                return num;
            }
        }

        return nums[0];
    }
};

解法二（摩尔投票法）：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums)
        {
            if (count == 0)
            {
                candidate = num;
            }

            if (num == candidate)
            {
                count++;
            }
            else
            {
                count--;
            }
        }

        return candidate;
    }
};

核心思想

这题最直接的做法是统计每个数字出现的次数。

因为多数元素出现次数大于：

⌊ n / 2 ⌋

所以只要某个元素计数超过 n / 2，它就是答案。

这就是哈希计数法。

但进阶要求是：

• 时间复杂度 O(n)
• 空间复杂度 O(1)

这时就要使用 摩尔投票法。

摩尔投票法的核心思想是：

每次让一个多数元素和一个非多数元素互相抵消，最后剩下的一定还是多数元素。

因为多数元素的数量超过数组长度的一半，所以其他所有元素加起来也没有它多。

即使每一个非多数元素都拿来抵消一个多数元素，多数元素最后也一定还会剩下。

哈希计数法

哈希计数法很好理解。

用哈希表 cnt 统计每个元素出现的次数：

cnt[num]++;

如果某个元素出现次数超过：

n / 2

就直接返回。

这个方法的优点是直观，缺点是需要额外空间存储计数。

摩尔投票法

摩尔投票法维护两个变量：

int candidate;
int count;

其中：

• candidate 表示当前候选的多数元素
• count 表示当前候选元素的“票数优势”

遍历数组时：

1. 如果 count == 0

说明当前没有候选人，或者之前的候选人已经被完全抵消。

这时把当前数字设为新的候选人：

candidate = num;

2. 如果当前数字等于候选人

说明候选人多获得一票：

count++;

3. 如果当前数字不等于候选人

说明当前数字可以和候选人抵消一票：

count--;

最终剩下的 candidate 就是多数元素。

为什么投票抵消是对的

假设数组中的多数元素是 x。

因为 x 出现次数大于 n / 2，所以：

x 的数量 > 非 x 的数量

如果我们每次拿一个 x 和一个非 x 抵消，那么最多只能抵消掉所有非 x。

但因为 x 的数量更多，所以抵消结束后，x 一定还会剩下。

摩尔投票法做的事情，本质上就是不断删除一对不同的元素。

删除一对不同元素不会改变多数元素的身份。

原因是：

• 如果删除的是一个多数元素和一个非多数元素，那么多数元素仍然比其他元素更有优势。
• 如果删除的是两个都不是多数元素的不同元素，那么多数元素完全没有减少，更不影响结果。

所以经过不断抵消，最后剩下的候选人一定是原数组中的多数元素。

更形式化的理解

摩尔投票法可以看成维护一个“未被抵消的集合”。

遍历过程中：

• 如果当前数和 candidate 相同，就加入未抵消集合，count++
• 如果当前数和 candidate 不同，就拿它和一个 candidate 抵消，count--
• 如果 count 变成 0，说明当前未抵消集合被清空，下一个元素可以重新开始形成新的集合

在任意时刻，count 表示当前候选人在未抵消集合中的剩余数量。

因为多数元素出现次数超过一半，所以无论中间怎样分段抵消，它都不可能被所有其他元素完全抵消掉。

因此最后留下的候选人只能是多数元素。

正确性证明

我们证明摩尔投票法最终返回的 candidate 一定是多数元素。

结论 1：删除一对不同元素，不会改变多数元素

设多数元素是 x，数组长度为 n，x 的出现次数为 cntX。

根据题意：

cntX > n / 2

现在删除一对不同元素。

如果这一对中包含一个 x，那么删除后：

• x 的数量变为 cntX - 1
• 数组长度变为 n - 2

要证明 x 仍然是多数元素，需要证明：

cntX - 1 > (n - 2) / 2

由：

cntX > n / 2

两边同时减去 1：

cntX - 1 > n / 2 - 1

也就是：

cntX - 1 > (n - 2) / 2

所以 x 仍然是多数元素。

如果这一对中不包含 x，那么删除后：

• x 的数量不变
• 数组长度减少 2

此时 x 更不可能失去多数地位。

因此，删除一对不同元素不会改变多数元素。

结论 2：摩尔投票法等价于不断删除不同元素对

当当前数字和 candidate 不同时，代码执行：

count--;

这可以理解成当前数字和一个未抵消的 candidate 互相删除。

当 count == 0 时，说明当前维护的未抵消元素已经全部抵消完。

接下来遇到的新元素会成为新的候选人。

所以整个过程等价于不断从数组中删除一对不同的元素。

结论 3：最终剩下的候选人一定是多数元素

由结论 1 可知，删除不同元素对不会改变多数元素。

由结论 2 可知，摩尔投票法正是在执行这样的删除过程。

因为题目保证多数元素一定存在，所以所有可能的抵消结束后，多数元素一定还会剩下。

而算法最终保留下来的 candidate 就是未被完全抵消的元素。

因此 candidate 一定是多数元素。

举例理解

以：

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

为例。

遍历过程如下：

最终候选人是 2。

虽然中间候选人变成过 1，但由于 2 是真正的多数元素，最后还是会留下来。

复杂度分析

解法一

• 遍历数组一次
• 哈希表查询和更新平均为 O(1)
• 时间复杂度：O(n)
• 最坏情况下哈希表存储多个不同元素
• 空间复杂度：O(n)

解法二

• 遍历数组一次
• 时间复杂度：O(n)
• 只使用 candidate 和 count 两个变量
• 空间复杂度：O(1)

所以如果要求满足进阶条件，应使用摩尔投票法。