2013·41 主元素：从双重循环计数到摩尔投票

本文属于「从暴力解到最优解」专题。这道题的最优解是历年真题里最「反直觉」的一个——摩尔投票只用两个变量就找出了过半元素。但先别急着背它，暴力解在这道题上的地位比你想的稳。

题目

已知一个整数序列 $A = (a_{0}, a_{1}, \dots, a_{n - 1})$ ，其中 $0 \leq a_{i} < n$ （ $0 \leq i < n$ ）。若存在 $a_{p_{1}} = a_{p_{2}} = \dots = a_{p_{m}} = x$ 且 $m > n / 2$ （ $0 \leq p_{k} < n, 1 \leq k \leq m$ ），则称 $x$ 为 $A$ 的主元素。例如：

A = (0, 5, 5, 3, 5, 7, 5, 5)，则 5 为主元素；
A = (0, 5, 5, 3, 5, 1, 5, 7)，则 A 中没有主元素。

假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出 -1。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C、C++ 或 Java 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

题面写了「尽可能高效」——按总纲的分类，暴力解和最优解之间存在真实分差。总分 9 分。

第一步：把暴力解写对

主元素的定义就是「出现次数严格超过 n/2 的元素」。最直接的想法：对每个元素，从头到尾数一遍它出现了几次，谁过半谁就是答案；全部数完没人过半，输出 −1。

int majority(int A[], int n) {
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++)      // 从头数 A[i] 出现的次数
            if (A[j] == A[i]) cnt++;
        if (cnt * 2 > n) return A[i];    // 严格过半即为主元素
    }
    return -1;                            // 无任何元素过半
}

验证题面的两个例子：A = (0, 5, 5, 3, 5, 7, 5, 5)，数到 i=1 时 5 出现 5 次，5×2 = 10 > 8，返回 5 ✓；A = (0, 5, 5, 3, 5, 1, 5, 7)，5 最多出现 4 次，4×2 = 8 不大于 8，其余元素更少，返回 −1 ✓。

一个必须写对的细节：过半判定是严格大于。用 cnt * 2 > n 而非 cnt > n / 2 的浮点/截断纠结——整数乘法没有歧义；写成 >= 直接错，n=8 时出现 4 次不算主元素。

复杂度：双重循环，时间 $O (n^{2})$ ；只用 cnt 一个计数器，空间 $O (1)$ 。

它值多少分

按正确性/最优性两个维度（详见总纲）：

正确性：思想直白清楚、代码逻辑自洽、过半判定严格、找不到时按题面返回 −1、复杂度分析 $O (n^{2})$ 与实现一致——正确性维度的主体分拿得到。
最优性：题面「尽可能高效」的期望是 $O (n)$ 时间 + $O (1)$ 空间。 $O (n^{2})$ 够不到，这一档拿不到。

复杂度那一问照实写 $O (n^{2})$ ——分析与算法一致本身是正确性得分点，谎报反而丢正确性的分。对一道 9 分的题来说，这份暴力解交上去大头在手，丢的只是最优性小档。

暴力解的浪费在哪

用总纲的三个问题审一遍：

**有没有重复扫描？——有，而且形态很典型。**外层每换一个 i 就把整个数组从头扫一遍。更扎眼的是：5 在数组里出现了 5 次，「数 5 出现几次」这件事就被完完整整做了 5 遍——同一个值的每次出现都触发一轮相同的全表统计。

**有没有重算已知的东西？——有。**内层比较产生的「相等/不等」信息用完即弃，下一轮从零开始。

有没有放着性质不用？——有，而且是决定性的。「过半」远不止一个判定门槛，它本身是个极强的结构性质：如果主元素存在，它比其余所有元素加起来还要多。把任意一个主元素和任意一个非主元素配对抵消，抵消到最后主元素必然有剩余。这意味着根本不需要给每个值分别计数——只要维护「当前领先者和它的净票数」就够了。

顺着前两个浪费走，能到一个中间站：题面给了 $0 \leq a_{i} < n$ 的值域，开一个长度 n 的计数数组，值直接当下标，一遍扫描全部计完—— $O (n)$ 时间，但花掉 $O (n)$ 空间。它消灭了重复扫描，却没碰「过半」这个性质。把第三问也用上，就是摩尔投票。

智慧化改造：摩尔投票

**第一遍：投票互抵选候选。**维护候选 candidate 和净票数 count，从左到右扫：

count == 0：当前元素上位成为新候选，count = 1；
当前元素 == candidate：count++（同伴加票）；
当前元素 != candidate：count--（敌对抵消一票）。

若真主元素 x 存在，每一对 (x, 非 x) 抵消后至少还剩 1 张 x 的票，扫完 candidate 必是 x。

**第二遍：验证。**第一遍只保证「如果主元素存在，candidate 就是它」，不保证「candidate 一定是主元素」——没有主元素时 candidate 可能是某个撑到最后的普通元素。所以要再扫一遍数出 candidate 的真实出现次数，严格过半才输出，否则输出 −1。

int majority(int A[], int n) {
    int candidate = A[0];
    int count = 1;

    // ① 第一遍：投票互抵选出候选
    for (int i = 1; i < n; i++) {
        if (count == 0) {                  // 上一组票抵光，重启候选
            candidate = A[i];
            count = 1;
        } else if (A[i] == candidate) {
            count++;                       // 同伴：票数加
        } else {
            count--;                       // 敌对：相互抵消
        }
    }

    // ② 第二遍：验证候选的真实出现次数是否过半
    int times = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] == candidate) times++;
    }

    return (times * 2 > n) ? candidate : -1;
}

复杂度：两遍线性扫描合计 2n 步，时间 $O (n)$ ；只用 candidate、count、times 几个标量，空间 $O (1)$ 。这就是标准答案，两个维度全部拿满。

从暴力解升级过来，四个细节决定这 9 分能拿多满：

第二遍验证绝不能省——这是本题最高频的错点。拿题面第二个例子 A = (0, 5, 5, 3, 5, 1, 5, 7) 走一遍第一轮：5 会几度上位又几度被抵光，扫完 candidate = 5、净票数为 0；但 5 实际只出现 4 次，不过半。不验证就把「没有主元素」误判成「主元素是 5」。暴力解里「数出来的就是真实次数」是免费的，投票互抵后这个保证消失了，必须自己补回来——这是暴力升级最优时典型的「免费性质要重新自己买单」。
count == 0 时必须同时重置 candidate。只把 count 置 1 而不换候选，等于让已经被抵光的旧候选白拿一票，按错处理。
加减方向别写反。同伴 count++、敌对 count--；写反后整个投票语义颠倒。
输出约定照题面：找不到返回 −1，既不是 0 也不是别的哨兵值；过半判定沿用严格大于。

两版对照跑一遍

同一组输入 [0, 5, 5, 3, 5, 7, 5, 5]（答案 5），先看双重循环版——每个 i 都触发一轮完整的内层统计：

加载可视化中...

再看摩尔投票版——两遍线性扫描，全程只有 candidate 和 count 两个变量在变：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

计数数组：题面 $0 \leq a_{i} < n$ 保证值可以直接当下标，一遍计数一遍找过半， $O (n)$ 时间——思路正确拿正确性分，但 $O (n)$ 空间不如摩尔投票的 $O (1)$ ，最优性那档拿不到。它是「空间换时间」的标准动作，只是这道题存在不花空间也能线性的解。
排序后取中间：若主元素存在，排序后它必然覆盖中间位置， $O (n \log n)$ 可解——同样只拿正确性分。注意取出中间元素后仍要数一遍验证过半，和摩尔投票的第二遍是同一个道理。
哈希表：值域不受限时的通用计数方案，空间同样 $O (n)$ ，判分定位与计数数组相同。
升级空间：摩尔投票有推广形式——找「出现次数 > n/k」的所有元素，同时维护 k−1 个候选做抵消。考研只考 k = 2 的基础形式，但理解「抵消后必有剩余」这个核心论证后，推广是顺理成章的。

下一步

在 OJ 上把两版代码都提交跑一遍：ds-2013-41 主元素
回到题库看这道题的完整解析与错因：真题库 · 数据结构

2013·41 主元素：从双重循环计数到摩尔投票 ​

题目 ​

第一步：把暴力解写对 ​

它值多少分 ​

暴力解的浪费在哪 ​

智慧化改造：摩尔投票 ​

两版对照跑一遍 ​

等价方法与升级空间 ​

下一步 ​