题目描述
思路解析
一句话答案：LeetCode 169 多数元素的最优解是摩尔投票一次遍历：维护候选人 cand 和票数 count，遇到相同的数加一票、不同的数减一票、票数归零就换当前数做新候选。因为多数元素出现次数严格过半，怎么抵消都消不完，扫完留下的候选必是它，时间 O(n)、空间 O(1)。
这道题真正在问什么
给长度为 n 的数组，题目保证其中有一个元素出现次数超过 ⌊n/2⌋（严格过半），要求把它找出来。「保证存在」和「严格过半」是决定解法的两个前提：过半意味着这个元素比其余所有元素加起来还多，这份悬殊的差距正是后面投票抵消法的底气。
哈希计数和排序为什么不是最优
用哈希表数每个元素的出现次数，O(n) 时间就能找到答案，但要 O(n) 空间；排序后取中间位置的数也一定是多数元素（它过半，无论怎么排都会覆盖中点），但排序要 O(n log n)。当面试官追问「能不能 O(n) 时间加 O(1) 空间」时，这两条路都被堵死——需要一种只用常数个变量、扫一遍就能锁定多数派的办法，摩尔投票（Boyer-Moore 投票算法）就是为此而生。
摩尔投票：不同的数互相抵消
投票法的直觉是打擂台：让一个非多数元素和一个多数元素配对同归于尽，两边各消耗一个。多数元素比其余全部加起来还多，哪怕每个「杂牌」都精准地拉一个多数元素垫背，多数元素也必有剩余。落到代码上只要两个变量：cand 是当前押注的候选人，count 是它的净胜票——遇到相同的数票数加一，遇到不同的数票数减一，减到零说明前面这段完全打平，就换当前数当新候选、票数重置为一。
为什么最后站住的候选一定是答案
把数组按「count 归零的时刻」切成若干段，每个打平的段内部恰好完全抵消，而任何一段里多数元素至多占一半。它在全数组严格过半，被各段抵消掉的部分凑不够它的总数，所以最后必然剩下一段消不平、且盈余的是多数元素——它就是收尾时的 cand。反过来，如果题目不保证多数元素存在，这条推理的前提就塌了：最后的 cand 只是嫌疑人，必须再扫一遍数它的真实出现次数，确认是否真的过半。
复杂度与两个容易写错的点
时间 O(n)：数组扫一遍，每个元素只做一次比较和一次加减。空间 O(1)：全程只有 cand 和 count 两个变量，不开哈希表。实现上最常见的错：一是 count 归零时忘了换候选人，投票链条直接断掉；二是把「同票加一、异票减一」写反，候选人会被自己人抵消、被对手抬轿，结果完全错乱。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住两个变量：cand 是「现在押注的候选人」，count 是「它还剩多少票」。票数归零就换人，相同加票、不同减票。
开始投票前：还没有候选人 cand，票数 count=0。指针 i 还没出发。
指针 i 走到下标 0，这一格是 2。此刻票数为 0，没有候选人能压住它，于是它成为新候选人。
票数本是 0，于是 2 当选新候选人（标绿的就是它），票数 count 重置为 1。
指针 i 走到下标 1，这一格是 2。它和当前候选人一样，给候选人加一票。
它和候选人 2 相同，给候选人添一票，票数升到 2（标绿表示又一张支持票）。
指针 i 走到下标 2，这一格是 1。它和当前候选人不同，抵消候选人一票。
它和候选人 2 不同，互相抵消一票，候选人票数降到 1（标红表示一张反对票）。
指针 i 走到下标 3，这一格是 1。它和当前候选人不同，抵消候选人一票。
它和候选人 2 不同，互相抵消一票，候选人票数降到 0（标红表示一张反对票）。
指针 i 走到下标 4，这一格是 2。此刻票数为 0，没有候选人能压住它，于是它成为新候选人。
票数本是 0，于是 2 当选新候选人（标绿的就是它），票数 count 重置为 1。
指针 i 走到下标 5，这一格是 1。它和当前候选人不同，抵消候选人一票。
它和候选人 2 不同，互相抵消一票，候选人票数降到 0（标红表示一张反对票）。
指针 i 走到下标 6，这一格是 2。此刻票数为 0，没有候选人能压住它，于是它成为新候选人。
票数本是 0，于是 2 当选新候选人（标绿的就是它），票数 count 重置为 1。
指针 i 走到下标 7，这一格是 2。它和当前候选人一样，给候选人加一票。
它和候选人 2 相同，给候选人添一票，票数升到 2（标绿表示又一张支持票）。
指针 i 走到下标 8，这一格是 2。它和当前候选人一样，给候选人加一票。
它和候选人 2 相同，给候选人添一票，票数升到 3（标绿表示又一张支持票）。
一趟扫完，最后站住的候选人就是 2（标绿的就是它出现的位置，共 6 个，确实过半）。它就是多数元素。
三个高频追问：两个变量含义、不保证存在时的补救、以及与哈希/排序解法的对比。
参考代码
def majorityElement(nums): cand = None count = 0 # 候选人票数 for x in nums: if count == 0: # 没人了，换候选人 cand = x count = 1 elif x == cand: # 同票 +1 count += 1 else: # 异票 -1 count -= 1 return cand复杂度
- 时间：O(n)，指针 i 把数组从头到尾扫一遍，每个元素只处理一次
- 空间：O(1)，只用 cand 和 count 两个变量，不开额外哈希表
易错点
面试追问把动画讲成自己的话
追问cand 和 count 分别代表什么？
追问如果题目不保证多数元素一定存在呢？
追问除了摩尔投票还有别的解法吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找到所有数组中消失的数字
LeetCode 448 · 简单 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题