多数元素 图解题解
找出现超过一半的数，哈希表能做，但摩尔投票只用两个变量、一次扫描，空间直接打到 O(1)。
想象一场计票：手里只握一张「当前候选」和一个「票数」。遇到和候选相同的数，票数+1；遇到不同的数，票数-1；票数降到 0，就把候选换成当前这个数、票数重置为 1。不需要找谁来配对，只是顺序扫、顺序更新。题目保证多数派超过一半，哪怕候选途中被换掉，最终留在手里的必然还是那个多数元素。
这道题到底在问什么
- nums
- [2, 2, 1, 1, 1, 2, 2]
- 输出
- 2 （2 出现 4 次，4 大于 7 的一半）
最优解：一步一步想明白
- 3最直觉的做法：开一个哈希表，逐个数计数，谁先超过一半就是它。对，但要额外 O(n) 空间。能不能只用一个变量、扫一遍？
- 4多数派的票，比其它所有数加起来还多。让不同的数互相抵消，抵到最后还站着的，必然是多数派。
- 5候选 ＝ 空，票数 ＝ 0准备两个变量：当前候选是谁、它手里有多少票数。开局都为空。
- 6候选 ＝ 2，票数 ＝ 1票数是 0，就让当前的 2 上位当候选，记 1 票。
- 7候选 ＝ 2，票数 ＝ 2又遇到 2，和候选一样，给它加一票，票数变 2。
- 8候选 ＝ 2，票数 ＝ 1来了个 1，和候选 2 不同，抵消一票，票数降到 1。注意：候选不换，只是减票。
- 9候选 ＝ 2，票数 ＝ 0又一个 1，票数减到 0——前面这段 2 和 1 正好两两抵消干净，谁也没赢。
- 10候选 ＝ 1，票数 ＝ 1关键一步：票数归零了，就换候选——现在候选暂时变成 1。别慌，后面会被顶回来。
- 11候选 ＝ 1，票数 ＝ 0又来个 2，把候选 1 的票也抵消到 0。
- 12候选 ＝ 2，票数 ＝ 1最后一个 2，票数又是 0，候选换回 2。扫描结束。
- 13答案 ＝ 2中途候选一度变成 1，但 2 太多了，总能把它顶回来。最后的候选 2 就是答案。
- 14票数轨迹 ＝ 1 → 2 → 1 → 0 → 1 → 0 → 1把整趟连起来看：票数像潮水起落，归零处就是「换候选」的拐点。少数派只能把它打到 0，永远清不光，所以多数派 2 最后还站着。
- 15正确性来自题目条件：多数元素超过一半，比其它所有数加起来还多。一对一抵消，它永远消不完。
- 18一句话记住摩尔投票：归零换人、同加异减、剩者为王。
- 20用 nums ＝ [1, 1, 2] 跑一遍拿小例子 [1,1,2] 真跑：正解答案是 1。如果写成「一遇到不同就换候选」，扫到最后的 2 会把候选直接改成 2，返回 2，错。所以一定要「票数归零」才换人，不是遇异就换。
- 24过半（大于 n／2）一个候选，过 n／3 两个候选，过 n／k 就 k−1 个候选——同一套「归零换人、同加异减」骨架扩出去。想再练可让小欧出 LC229 陪你过一遍，或去通关训练里刷同型题。
⚠️ 容易写错的地方
✗ 错：一遇到不同的数就马上换候选
✓ 对：只有 票数 count 等于 0 时才换候选
抵消是「减一票」，不是立刻改人；减到 0 才轮下一个上位
✗ 错：同票 −1、异票 ＋1（加减写反）
✓ 对：同票 ＋1、异票 −1
要让多数派把票攒住、把少数派抵消干净，方向反了答案就错
✗ 错：不保证多数元素存在时也直接返回候选
✓ 对：通用情形要再扫一遍，数候选真实票数是否过半
摩尔投票只「选出」候选不验证；本题保证存在，才可省掉第二遍
完整代码（Python / C++ / Java）
Python
class Solution:
def majorityElement(self, nums):
cand = None
count = 0
for x in nums:
if count == 0:
cand = x
count += 1 if x == cand else -1
return candC++
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cand = 0, count = 0;
for (int x : nums) {
if (count == 0) cand = x;
count += (x == cand) ? 1 : -1;
}
return cand;
}
};Java
class Solution {
public int majorityElement(int[] nums) {
int cand = 0, count = 0;
for (int x : nums) {
if (count == 0) cand = x;
count += (x == cand) ? 1 : -1;
}
return cand;
}
}套路模板 · 摩尔投票骨架（挖空自填）
# 求「出现次数过半」的元素
cand, count = None, 0
for x in arr:
if count == 0: # ← 归零才换人
cand = x
# TODO 同票则 +1，异票则 -1
count += 1 if x == cand else -1
# 不保证存在时：再扫一遍验证 cand 是否过半
# return cand if arr.count(cand) > len(arr)//2 else -1// 求「出现次数过半」的元素
int cand = 0, count = 0;
for (int x : arr) {
if (count == 0) cand = x; // ← 归零才换人
count += (x == cand) ? 1 : -1; // 同加异减
}
// 不保证存在时：再扫一遍统计 cand 真实次数 > n/2
return cand;// 求「出现次数过半」的元素
int cand = 0, count = 0;
for (int x : arr) {
if (count == 0) cand = x; // ← 归零才换人
count += (x == cand) ? 1 : -1; // 同加异减
}
// 不保证存在时：再扫一遍统计 cand 真实次数 > n/2
return cand;复杂度
时间复杂度
O(n)
只扫一遍数组，每个数做一次比较加减
空间复杂度
O(1)
只用候选、票数两个变量，不开哈希表
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 多数元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么摩尔投票一定对？给我证明一下。+
多数元素出现次数大于 ⌊n／2⌋，意味着它比其它所有数加起来还多。把「相同记同伙、不同就一换一抵消」看成配对：每次抵消都消掉一个多数派和一个非多数派。非多数派总数不足一半，永远先被消光，多数派必有剩余，所以最终候选就是它。
如果不保证多数元素存在，怎么改？+
摩尔投票只负责「选候选」不验证。加第二遍遍历，统计候选在数组里的真实出现次数，若大于 ⌊n／2⌋ 才返回，否则返回「不存在」。仍是 O(n) 时间、O(1) 空间。
还有别的 O(n) 解吗？各自代价？+
哈希计数：O(n) 时间但 O(n) 空间。排序后取中位数 nums[n／2]：O(n log n) 时间、O(1) 额外空间。位运算按 32 位逐位统计多数：O(32n) 时间、O(1) 空间。摩尔投票是唯一 O(n) 时间＋O(1) 空间的，所以最优。
进阶：求出现次数大于 ⌊n／3⌋ 的所有数怎么办？+
大于 n／3 的数最多 2 个，于是维护「两个候选＋两套票数」：来的数等于某候选就给谁加票，否则若有票数为 0 的候选就顶上去，再不然两个候选票数同时减一。最后必须再扫一遍验证这两个候选是否真的过 n／3。就是 LC229。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。