多数元素

最直觉的做法：开一个哈希表，逐个数计数，谁先超过一半就是它。对，但要额外 O(n) 空间。能不能只用一个变量、扫一遍？

多数派的票，比其它所有数加起来还多。让不同的数互相抵消，抵到最后还站着的，必然是多数派。

准备 · 两个变量：准备两个变量：当前候选是谁、它手里有多少票数。开局都为空。

第 1 个 · 票数为 0 就立候选：票数是 0，就让当前的 2 上位当候选，记 1 票。

第 2 个 · 同票加一：又遇到 2，和候选一样，给它加一票，票数变 2。

第 3 个 · 异票减一：来了个 1，和候选 2 不同，抵消一票，票数降到 1。注意：候选不换，只是减票。

第 4 个 · 异票减一，归零：又一个 1，票数减到 0——前面这段 2 和 1 正好两两抵消干净，谁也没赢。

第 5 个 · 票数为 0 就换候选：关键一步：票数归零了，就换候选——现在候选暂时变成 1。别慌，后面会被顶回来。

第 6 个 · 异票减一，又归零：又来个 2，把候选 1 的票也抵消到 0。

第 7 个 · 票数为 0 换回 2：最后一个 2，票数又是 0，候选换回 2。扫描结束。

结束 · 候选就是答案：中途候选一度变成 1，但 2 太多了，总能把它顶回来。最后的候选 2 就是答案。

灵魂帧慢放 · 票数曲线：把整趟连起来看：票数像潮水起落，归零处就是「换候选」的拐点。少数派只能把它打到 0，永远清不光，所以多数派 2 最后还站着。

正确性来自题目条件：多数元素超过一半，比其它所有数加起来还多。一对一抵消，它永远消不完。

一句话记住摩尔投票：归零换人、同加异减、剩者为王。

雷区实演 · 遇异票就换人会翻车：拿小例子 [1,1,2] 真跑：正解答案是 1。如果写成「一遇到不同就换候选」，扫到最后的 2 会把候选直接改成 2，返回 2，错。所以一定要「票数归零」才换人，不是遇异就换。

面试追问：证明、通用化、别的解法、进阶版——这四问几乎是 169 的固定追问套餐。

迁移阶梯：过半（大于 n／2）一个候选，过 n／3 两个候选，过 n／k 就 k−1 个候选——同一套「归零换人、同加异减」骨架扩出去。想再练可让小欧出 LC229 陪你过一遍，或去通关训练里刷同型题。

边界三连：单元素直接返回；多数派在前、在后都能选对——摩尔投票和多数派出现的位置无关。