题目描述
数组里有个数出现次数超过一半（> ⌊n/2⌋），找出它。题目保证它一定存在。
nums = [2, 2, 1, 1, 1, 2, 2]
输出 = 2 （2 出现 4 次 > 7/2）
思路解析
多数派的票比其它所有数加起来还多。让不同的数互相抵消，抵到最后还站着的，必然是多数派。
准备：准备两个变量：当前候选是谁、它手里有多少票数。开局都为空。
第 1 个 · 票数为 0 → 立候选：票数是 0，就让当前的 2 上位当候选，并记 1 票。
第 2 个 · 同票 +1：又遇到 2，和候选一样，给它加一票，票数变 2。
第 3 个 · 异票 -1：来了个 1，和候选 2 不同，抵消一票，票数降到 1。注意：候选不换，只是减票。
第 4 个 · 异票 -1 → 归零：又一个 1，票数减到 0——前面这段 2 和 1 正好两两抵消干净，谁也没赢。
第 5 个 · 票数为 0 → 换候选：关键一步：票数归零了，就换候选——现在候选暂时变成 1。别慌，后面会被顶回来。
第 6 个 · 异票 -1 → 归零：又来个 2，把候选 1 的票也抵消到 0。
第 7 个 · 票数为 0 → 换回 2：最后一个 2，票数又是 0，候选换回 2。扫描结束。
结束 · 候选就是答案：中途候选一度变成 1，但 2 太多了，总能把它顶回来。最后的候选 2 就是答案。
正确性来自题目条件：多数元素超过一半，比其它所有数加起来还多。一对一抵消，它永远消不完。
想清楚「归零换人」这一步，你就真懂摩尔投票了。
参考代码（Python）
Python
1def majorityElement(nums):
2 candidate, count = None, 0 # 候选人、它的票数
3 for x in nums:
4 if count == 0: # 票数归零，才换候选
5 candidate = x
6 count += 1 if x == candidate else -1 # 同 +1，异 -1
7 return candidate # 题目保证多数元素一定存在复杂度分析
- 时间复杂度：O(n) —— 只扫一遍数组
- 空间复杂度：O(1) —— 只用候选、票数两个变量，不开哈希表
套路模板
记住这个「票数归零换人、同加异减」的模板，求过半元素一招通用。
Python
1candidate, count = None, 0
2for x in arr:
3 if count == 0:
4 candidate = x
5 count += 1 if x == candidate else -1
6# candidate = 出现次数过半的那个易错点
- 错误写法：一遇到不同的数就马上换候选 → 正确写法：只有 票数 count == 0 时才换候选（抵消是「减一票」，不是立刻改人；减到 0 才轮下一个上）
- 错误写法：同票 -1、异票 +1（加减写反） → 正确写法：同票 +1、异票 -1（要让多数派把票攒住、把少数派抵消干净，方向不能反）
- 错误写法：不保证多数元素存在时也直接返回候选 → 正确写法：通用情形要再扫一遍、数候选真实票数是否过半（摩尔投票只「选出」候选不验证；本题保证存在才可省掉第二遍）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。