如何找出数组中的多数元素？（摩尔投票法，LeetCode 169）

简化版

找出数组中的多数元素——出现次数超过 ⌊n/2⌋（严格过半）的元素，题目保证存在。最优解是摩尔投票法（Boyer-Moore Voting）：维护一个「候选人 candidate」和「票数 count」，遍历数组，遇到和候选人相同的票数 +1，不同的票数 -1；票数减到 0 就换当前元素当新候选人。因为多数元素过半，最后剩下的候选人一定是它。O(n) 时间、O(1) 空间。

详细版

int majorityElement(int[] nums) {
    int candidate = 0, count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;       // 票数归零，换当前元素当候选人
        }
        count += (num == candidate) ? 1 : -1;   // 同票 +1，异票 -1
    }
    return candidate;              // 多数元素过半，最终候选人即是
}

摩尔投票核心：相同 +1、不同 -1，票数归零就换候选人。
为什么对：多数元素超过半数，它的「+1」总量压倒所有其他元素的「-1」总量，最终留存。
对比其他解法：哈希计数 O(n) 时间 O(n) 空间；排序后取中位数 O(n log n)。摩尔投票 O(n)/O(1) 最优。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、题意：严格过半的元素

多数元素定义为出现次数 > ⌊n/2⌋（严格超过一半，不是「最多」）。题目保证一定存在这样的元素。正因为「严格过半」这个强条件，才有摩尔投票这种 O(1) 空间的神奇解法。

二、几种解法对比

哈希计数：HashMap 统计每个元素次数，返回次数 > n/2 的。O(n) 时间、O(n) 空间。
排序取中位数：排序后，因为多数元素过半，下标 n/2 处的元素必然是它（过半元素一定占据中间位置）。O(n log n) 时间。
摩尔投票：O(n) 时间、O(1) 空间，最优。下面重点讲。

三、摩尔投票法：抵消的智慧

摩尔投票的核心思想是**「对拼消耗」**：维护一个候选人和它的票数。

遍历数组，若 count == 0，把当前元素设为新候选人，票数从 0 开始。
若当前元素等于候选人，count++（支持者 +1）。
若不等于候选人，count--（反对者，抵消一票）。

直觉：把多数元素的每次出现看成「+1 票」，其他所有元素看成「-1 票」。因为多数元素超过半数，它的 +1 总数严格大于所有其他元素 -1 的总数，两两抵消后，最后一定剩下多数元素当候选人、票数为正。

四、为什么抵消后一定剩多数元素

设多数元素出现 m 次，m > n/2，其余元素共 n - m < n/2 次。摩尔投票本质是：每一次「候选人被减到 0 换人」，都消耗掉了一对「不同的元素」（一个多数、一个非多数，或两个非多数）。因为多数元素数量 m 严格大于其余所有元素之和 n-m，无论怎么两两抵消，多数元素都消耗不完，必有剩余，成为最终候选人。这就是「过半」条件的威力——它保证了抵消后多数元素不会被清空。

五、走一遍例子

nums = [2,2,1,1,1,2,2]（多数元素是 2，出现 4 次 > 3）：

2：count=0 → candidate=2, count=1
2：==2 → count=2
1：≠2 → count=1
1：≠2 → count=0
1：count=0 → candidate=1, count=1
2：≠1 → count=0
2：count=0 → candidate=2, count=1

最终 candidate=2。✔ 尽管中途候选人换过，多数元素 2 最后胜出。

六、抵消证明依赖“严格过半”

把一个多数元素与一个非多数元素配成一对并删除。由于多数元素数量严格大于所有其他元素总数，无论怎样做异类配对，最终至少剩一个多数元素；摩尔投票的 count-- 就是在流式执行这种抵消。

数组 [2,2,1,1,1,2,2]
读 2: candidate=2,count=1
读 2: count=2
读 1: count=1
读 1: count=0（抵消两对）
读 1 后重选 1，随后两个 2 最终令 candidate=2
2 出现 4/7，确为多数

校验维度	本题必须保持的结论
循环/递推不变量	当前候选及 count 表示扫描前缀抵消异类配对后剩余的同值票数。
边界条件	题设若不保证多数存在，第一遍只给候选，必须第二遍验证频次是否大于 n/2。
复杂度与代价	O(n) 时间 O(1) 空间；相比哈希表不记录所有频次。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：当前候选及 count 表示扫描前缀抵消异类配对后剩余的同值票数。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“数组 [2,2,1,1,1,2,2]”开始手推，最后应得到“2 出现 4/7，确为多数”。
边界复核：题设若不保证多数存在，第一遍只给候选，必须第二遍验证频次是否大于 n/2。
代价复核：O(n) 时间 O(1) 空间；相比哈希表不记录所有频次。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“当前候选及 count 表示扫描前缀抵消异类配对后剩余的同值票数。”这条正确性主线不能省。

八、常见误区与追问

误区：count 表示候选的真实出现次数。 它是抵消后的净票数，不是原数组频次。
误区：候选中途变化说明算法不稳定。 前缀可被完全抵消时重选不影响剩余后缀中多数元素的最终优势。
误区：没有多数元素时返回值仍一定正确。 无保证版本必须第二遍计数验证，否则只得到一个候选。
追问：为什么阈值必须严格大于 n/2？ 只有此时一个元素数量大于所有其他元素总和，异类抵消后必有剩余。
追问：寻找超过 n/3 的元素如何推广？ 最多有两个候选，维护两个候选及计数，最后再验证。
追问：排序法的候选在哪里？ 若多数存在，排序后下标 n/2 必落在多数元素连续区间内。

九、加强记忆

多数元素（出现 > ⌊n/2⌋）= 摩尔投票法，O(n) 时间 O(1) 空间（优于哈希 O(n) 空间、排序 O(n log n)）。维护候选人 + 票数：count==0 时换当前元素当候选人；元素等于候选人 count++、不等 count--。原理：多数元素过半，它的「+1」严格多于其他所有「-1」，两两抵消后必有剩余，最终候选人就是它。（另一简单解法：排序后取下标 n/2 的元素，过半元素必占中位。）核心：同票加、异票减、归零换人，过半者笑到最后。

简化版

详细版