题目

已知一个整数序列 A = (a₀, a₁, …, aₙ₋₁)，其中 0 ≤ aᵢ < n（0 ≤ i < n）。若存在 a_{p₁} = a_{p₂} = ⋯ = a_{p_m} = x 且 m > n/2（0 ≤ p_k < n，1 ≤ k ≤ 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) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：摩尔投票法（Boyer-Moore Voting）——一遍扫描出"候选主元素"，再扫一遍验证它的真实出现次数是否真的 > n/2。

第一遍：选候选

维护两个变量：候选 candidate 和计票 count。从左到右扫描数组：

• count == 0：把当前元素当作新候选，count = 1；
• 当前元素 == candidate：count++（同伴+1）；
• 当前元素 != candidate：count--（敌对方+1，相互抵消）。

扫完一遍剩下的 candidate 可能是主元素。

为什么这套"投票互抵"出来的候选是合理的？

如果数组里真有主元素 x（出现次数 > n/2），那 x 在数组中比"所有其他元素加一起"都多。每一对（x, 非x）相互抵消后，至少还有 1 张 x 的票剩下，最终 candidate 就是 x。反之若没有真主元素，candidate 是谁不确定（可能是某个"孤狼"），因此必须再扫一遍验证。

第二遍：验证

数一遍 candidate 在数组中的实际出现次数。若 > n/2，输出 candidate；否则输出 −1。

(2) 代码实现

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;
}

关键点说明：

• 第二遍验证不可省略：第一遍只能保证"如果有主元素，candidate 就是它"，但不能保证"candidate 一定是主元素"。例如 A = (0, 1, 2, 3) 没有主元素，第一遍会输出 candidate = 3，但 3 出现 1 次而非 > 2 次，必须第二遍打回。
• count 用乘 2 比较避免除法：times * 2 > n 比 times > n / 2.0 更稳——后者在 n 为奇数时要小心整数除法截断（n/2 在 n=5 时是 2，主元素需 ≥ 3 即 times > 2.5，写 times > n/2 也对，但 times * 2 > n 更直接）。
• 不要尝试用排序：排序后中位数一定是主元素（如果存在），可解为 O(n log n)，但摩尔投票 O(n) 显然更优。
• 不要用哈希表：题面 0 ≤ a_i < n，用 cnt 数组确实可行（O(n) 时间 + O(n) 空间），但摩尔投票 O(1) 空间 更高效，是本题"尽可能高效"的最优解。

(3) 复杂度分析

• 时间复杂度 ：两遍线性扫描。
• 空间复杂度 ：只用 candidate、count、times、i 几个标量，与 n 无关。

编者注（生僻术语）：摩尔投票法（Boyer-Moore Majority Vote）由 Boyer 和 Moore 在 1981 年提出，是「找出现次数严格 > n/2 的元素」的经典 O(n) 时间 + O(1) 空间算法。它有推广形式可以找"出现次数 > n/k"的所有元素（保留 k−1 个候选，类似投票），考研只考最基础的 k = 2 形式。