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;
}

思路简要说明：

边扫边计数：map 里存"这个数出现了几次"
随时检查：每加一次就看看次数有没有超过 n / 2，超过就是答案
**时间复杂度 O(n)**，空间 O(n)

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];
}

思路简要说明：

先排序：相同的元素会被排到一起
直接取中间：下标 n / 2 上的元素就是多数元素
**时间复杂度 O(n log n)**，空间 O(1)（不算排序本身的开销）

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;
}

思路简要说明：

维护一个候选人：candidate 是当前"领先"的那个数
count 是它的净票数：遇到相同的就 +1，遇到不同的就 −1
净票数归零就换人：说明候选人被抵消光了，让下一个数上台
最后剩下的就是多数元素
**时间复杂度 O(n)**，空间 O(1)

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 两个变量。

六、总结

方法	时间	空间	关键点
哈希表计数	O(n)	O(n)	直接统计每个数的出现次数
排序取中间	O(n log n)	O(1)	过半 ⇒ 必然占据下标 `n/2`
摩尔投票法	O(n)	O(1)	过半 ⇒ 抵消不完，最后剩的必是它