多数元素 II

假设有 3 个数都超过 n／3，那它们次数之和 > 3 × n／3 = n，比整个数组还长，不可能。所以答案至多 2 个——这是用「两个候选」的底气。

169 题只用一个候选找过半的数;这里要找过 1／3 的，所以备两个候选 cand1／cand2，各带一个票数。规则只多了一条:当前数和两个候选都不同、且都还有票时，两边各减一票。

准备 · 两个候选两个票数：开局两个候选都为空、票数都是 0。下面让一个指针从左往右逐个扫描，每扫一个就按规则更新这四个变量，盯住它们怎么变。

扫 nums[0]＝1 · 票1为0 → 立候选：第 1 个数 1。两个候选都还空着，先看 cand1 的票数是 0 → 让 1 占住 cand1，记 1 票。

扫 nums[1]＝1 · 同 cand1 → 票1加一：又一个 1，和 cand1 相同，给它加一票，票1 变 2。

扫 nums[2]＝1 · 同 cand1 → 票1加一：再一个 1，cand1 票数涨到 3。前三个数都是 1，cand1 攒了厚厚一沓票。

扫 nums[3]＝3 · 票2为0 → 立候选：来了个 3，和 cand1(=1) 不同。这时看 cand2 的票数是 0 → 让 3 占住 cand2，记 1 票。注意:没去减 cand1 的票，因为还有空候选位可占。

扫 nums[4]＝3 · 同 cand2 → 票2加一：又一个 3，和 cand2 相同，票2 加到 2。现在 cand1＝1(3 票)、cand2＝3(2 票)，势均力敌。

扫 nums[5]＝2 · 都不同 → 两票各减一：关键一步:来了个 2，和两个候选(1、3)都不同，而且两边都还有票。规则规定:两个票数各减一(2 自己也没站住)。候选不换，只是两边各掉一票。

扫 nums[6]＝2 · 都不同 → 两票各减一：再一个 2，还是都不同，两票再各减一。票2 被减到 0——cand2(=3) 的位子空出来了。

扫 nums[7]＝2 · 票2为0 → 2 占 cand2：最后一个 2。cand1 还是 1(还有 1 票)，但 cand2 的位子空着 → 2 趁机占住 cand2，记 1 票。扫描结束:候选定格为 cand1＝1、cand2＝2。

一遍扫完 · 得到两个候选：第一遍只「选出」了两个嫌疑人 1 和 2。但摩尔投票的票数是抵消后的余票，不是真实出现次数——万一数组里根本没有过 1／3 的数，也会硬选出两个。所以必须再扫一遍，数它们的真实次数。

第二遍验证 · 数 cand1＝1 的真实次数：第二遍开始，先验证 cand1＝1。准备一个真实计数 v1＝0，从头逐个看是不是 1。

数 1 · 扫到 nums[0]＝1：第一格是 1，和 cand1 相同，真实计数 v1 加到 1。接着往后数。

数 1 · nums[0..2] 都是 1：数下来，1 一共出现 3 次(前三格)，后面都不是 1。v1＝3。

验证 cand1 · 3 ＞ 2 ✓ 入选：判定:v1＝3，3 ＞ 2 成立 → 1 确实是过 1／3 的数，收进答案。

第二遍验证 · 数 cand2＝2 的真实次数：同样地验证 cand2＝2。重置真实计数 v2＝0，再从头数是不是 2。

数 2 · nums[5..7] 都是 2：2 出现在最后三格，一共 3 次。v2＝3。

验证 cand2 · 3 ＞ 2 ✓ 入选：v2＝3，3 ＞ 2 也成立 → 2 入选。两个候选都通过验证，最终答案 [1, 2]，收工!

再看一例 · nums = [3,2,3] 体会「为什么必须验证」：换个小例子 [3,2,3] 走一遍，重点看第一遍会选出两个候选，但只有一个能通过验证——这就是第二遍存在的意义。

[3,2,3] 第一遍 · 3 占 cand1、2 占 cand2：3 占 cand1;2 看到 cand2 空着也占了 cand2;最后的 3 让票1 涨到 2。第一遍硬选出两个候选 {3, 2}——可 2 其实只出现 1 次。

[3,2,3] 第二遍 · 验证淘汰假候选：第二遍真实计数:3 出现 2 次 ＞ 1 入选;2 只出现 1 次，不过 1／3，被淘汰。最终 [3]。看，不验证就会把假候选 2 也交上去——这就是第二遍的价值。

边界三连：先想清楚「有假候选要淘汰」「单元素」「答案为空」三种边界，第二遍验证就把它们全兜住了。

面试追问：把「最多 2 个」「为何要二次验证」「如何推广到 1／k」讲清楚，是这题面试的得分点。