摩尔投票算法 (Boyer-Moore Voting Algorithm)¶

摩尔投票算法（Boyer-Moore Majority Vote Algorithm），由 Robert S. Boyer 和 J Strother Moore 于 1981 年提出，是一种在流式数据（Streaming Data）或海量数据场景下，以严格 \(\mathcal{O}(N)\) 线性时间与严格 \(\mathcal{O}(1)\) 额外空间寻找序列中“绝对众数（Majority Element）”的绝妙算法。

除了解决经典的基础众数问题外，该算法还可以推广至寻找出现次数超过 \(\lfloor N/k \rfloor\) 的高频元素（Misra-Gries 算法），甚至能凭借其罕见的半群结合律（Associativity）与线段树结合，在线高效解决复杂的区间绝对众数查询。

1. 核心问题定义与 Intuition (同归于尽消去法)¶

1.1 绝对众数的数学定义¶

对于一个包含 \(N\) 个元素的序列，若存在某个元素 \(x\)，其在序列中的出现次数 \(count(x)\) 满足：

\[ count(x) > \left\lfloor \frac{N}{2} \right\rfloor \]

则称 \(x\) 为该序列的绝对众数（Majority Element）。根据抽屉原理（Pigeonhole Principle），一个序列中最多只能存在一个绝对众数。

1.2 核心算法直觉 (Intuition)¶

常规方法如果使用哈希表计数，需要 \(\mathcal{O}(N)\) 额外内存；如果排序后取中位数，需要 \(\mathcal{O}(N \log N)\) 时间。

摩尔投票算法采用了一种极具哲学美感的物理隐喻——“不同元素两两同归于尽（Pairwise Elimination）”：

核心直觉：想象全序列的每个元素都是一个士兵。如果两个士兵属于不同阵营（数值不同），他们就同归于尽、同归于虚无。如果序列中存在一个绝对众数，其人数超过了全场总人数的一半（\(> N/2\)）。那么，即使全场所有非众数阵营联合起来，每一个人都拉走一个众数士兵同归于尽，最终剩下的幸存者阵营必定且唯一定属于绝对众数！

2. 基础摩尔投票算法 (出现次数 \(> \lfloor N/2 \rfloor\))¶

2.1 算法执行机制与不变量¶

我们只需在遍历过程中维护两个变量：

candidate：当前占据优势地位的候选人；
count：该候选人的净胜票数（血量 / 票数优势）。

流程规则：¶

初始时 count = 0，候选人未定；
遍历输入序列中的每一个元素 \(x\)：
若 count == 0，说明此前的所有对拼已经全部同归于尽。当前元素 \(x\) 成为新的候选人，并置 count = 1；
若 count > 0：
- 若 \(x == candidate\)，阵营增援，血量增加：count++；
- 若 \(x \ne candidate\)，异己对抗，一换一抵消：count--。
遍历结束后，剩下的 candidate 即为候选幸存者。

2.2 两阶段执行模型与验资必要性¶

[!WARNING] 关键细节：幸存者不一定是合法的绝对众数！ 摩尔投票第一阶段的结论是：“如果序列存在绝对众数，则它必是最终幸存的 candidate”。但如果序列本身不存在绝对众数（例如 [1, 2, 3]），算法仍然会输出某一个幸存者（如 3）。

因此，标准摩尔投票算法严格包含两个阶段：

第一阶段（选举对拼，Vote Phase）：单次遍历，筛选出唯一的疑似候选人；
第二阶段（验资确认，Validation Phase）：若题目不保证一定存在绝对众数，必须再跑一次 \(\mathcal{O}(N)\) 的计数统计，核实该候选人的总票数是否真的严格大于 \(\lfloor N/2 \rfloor\)。

2.3 基础模板实现 (C++)¶

#include <vector>
#include <optional>

class MajorityVote {
public:
    // 寻找绝对众数 (> floor(n / 2))
    // 若保证存在绝对众数，则无需第二阶段
    // 时间复杂度: O(N), 空间复杂度: O(1)
    static std::optional<int> find_majority(const std::vector<int> &nums) {
        if (nums.empty()) return std::nullopt;

        // ========== 阶段一：投票对拼选举 ==========
        int candidate = 0;
        int count = 0;

        for (int x : nums) {
            if (count == 0) {
                candidate = x;
                count = 1;
            } else if (x == candidate) {
                count++;
            } else {
                count--;
            }
        }

        // ========== 阶段二：验资确认 (Validation) ==========
        int actual_count = 0;
        for (int x : nums) {
            if (x == candidate) actual_count++;
        }

        if (actual_count > static_cast<int>(nums.size()) / 2) {
            return candidate;
        }
        return std::nullopt; // 不存在绝对众数
    }
};

3. 广义摩尔投票算法 (Misra-Gries 算法：出现次数 \(> \lfloor N/k \rfloor\))¶

3.1 抽屉原理推广与多候选人模型¶

如果将问题推广为：找出序列中所有出现次数严格大于 \(\lfloor N/k \rfloor\) 的元素（其中 \(k \ge 2\)）。

根据抽屉原理：

若存在 \(k\) 个出现次数都严格大于 \(\lfloor N/k \rfloor\) 的互异元素，则它们的总出现次数至少为：

\[ k \times \left( \left\lfloor \frac{N}{k} \right\rfloor + 1 \right) > k \times \frac{N}{k} = N \]

这与序列总长度为 \(N\) 产生不可调和的矛盾。因此，出现次数严格大于 \(\lfloor N/k \rfloor\) 的元素个数至多只有 \(k - 1\) 个！

3.2 抵消规则：\(k\) 个互异元素一同消除¶

在基础算法中，我们是让 2 个不同元素“两两同归于尽”。推广到 \(k\) 时，我们的抵消规则升级为：只要集齐 \(k\) 个互不相同的元素，就让这 \(k\) 个元素各出一个，一同同归于尽！

我们只需同时维护 \(k - 1\) 个候选人及其对应的计票器：

遇到元素 \(x\) 时：
若 \(x\) 已经与某个已存在的候选人匹配，该候选人的票数自增；
若 \(x\) 不匹配现有任何候选人，但当前有空闲槽位（某个候选人的票数为 0），则将其扶正为新候选人，票数置为 1；
若 \(x\) 不匹配且所有 \(k - 1\) 个槽位全部被占满：说明此时集齐了 \(k\) 个互不相同的元素！将当前所有的 \(k - 1\) 个候选人的计票器同时减 1（与 \(x\) 一同被消除）。
第一阶段结束后，剩下的 \(k - 1\) 个候选人进入第二阶段，逐一统计真实频次验资，筛选出频次 \(> \lfloor N/k \rfloor\) 的有效答案。

3.3 经典实战：LeetCode 229 (出现次数 \(> \lfloor N/3 \rfloor\))¶

对应 \(k = 3\)，答案最多只有 \(3 - 1 = 2\) 个，维护两个候选人和两个计数器：

#include <vector>

class Solution {
public:
    std::vector<int> majorityElement(std::vector<int>& nums) {
        int n = nums.size();
        int cand1 = 0, count1 = 0;
        int cand2 = 0, count2 = 0;

        // 阶段一：双候选人抵消配对
        for (int x : nums) {
            if (count1 > 0 && x == cand1) {
                count1++;
            } else if (count2 > 0 && x == cand2) {
                count2++;
            } else if (count1 == 0) {
                cand1 = x;
                count1 = 1;
            } else if (count2 == 0) {
                cand2 = x;
                count2 = 1;
            } else {
                // 集齐 3 个不同元素，同时扣除血量
                count1--;
                count2--;
            }
        }

        // 阶段二：验资核实
        int actual1 = 0, actual2 = 0;
        for (int x : nums) {
            if (count1 > 0 && x == cand1) actual1++;
            else if (count2 > 0 && x == cand2) actual2++;
        }

        std::vector<int> ans;
        if (count1 > 0 && actual1 > n / 3) ans.push_back(cand1);
        if (count2 > 0 && actual2 > n / 3) ans.push_back(cand2);
        return ans;
    }
};

4. 高阶拓展：摩尔投票的半群结合律与线段树结合¶

在算法竞赛中，摩尔投票最令人震撼的高阶应用，是它具备半群结合律（Associativity），能够与线段树（Segment Tree）无缝结合，在线解决区间绝对众数查询问题！

4.1 摩尔投票元组的结合律证明¶

将一个区间的投票状态形式化定义为一个二元组 \((c, w)\)：

\(c\)：当前区间最终竞选出的候选人；
\(w\)：该候选人的净剩余票数（优势）。

对于两个相邻的不相交区间 \(A\) 和 \(B\)，其各自的状态分别为 \((c_A, w_A)\) 和 \((c_B, w_B)\)。我们定义合并算子 \(\oplus\) 如下：

\[ (c_A, w_A) \oplus (c_B, w_B) = \begin{cases} (c_A, w_A + w_B), & \text{若 } c_A = c_B \\ (c_A, w_A - w_B), & \text{若 } c_A \ne c_B \text{ 且 } w_A \ge w_B \\ (c_B, w_B - w_A), & \text{若 } c_A \ne c_B \text{ 且 } w_A < w_B \end{cases} \]

定理（结合律）：算子 \(\oplus\) 满足结合律，即对任意三个区间 \(A, B, C\)：

\[ ((A \oplus B) \oplus C) = (A \oplus (B \oplus C)) \]

若整个合并后的区间存在绝对众数 \(M\)，则合并计算得到的候选人必为 \(M\)。

证明要点：因为合并算子的本质仍然是“不同阵营两两抵消”。无论抵消操作是在区间内部发生、还是跨区间发生，由于抵消总是成对移除不同元素，全区间的绝对众数其净票数始终严格大于 0，因此最终幸存者绝不可能被彻底抵消出局。

4.2 区间绝对众数在线查询算法架构 (LeetCode 1157 模型)¶

问题：给定静态数组，多次在线查询区间 \([L, R]\) 内出现次数是否至少为 \(threshold\)（\(threshold > (R - L + 1) / 2\)）。

解决方案：

线段树维护二元组 \((c, w)\)：
叶子节点 \(i\) 存储 \((nums[i], 1)\)；
内部节点利用上述 \(\oplus\) 规则在 \(\mathcal{O}(1)\) 内合并左右儿子；
单次区间查询在 \(\mathcal{O}(\log N)\) 内返回区间 \([L, R]\) 的疑似候选人 \(cand\)；
离散化下标数组二分验资：
预处理建立每个数值的所有出现下标的有序列表 pos[val]；
对候选人 \(cand\) 的下标列表进行两次 std::lower_bound / std::upper_bound 二分搜索，在 \(\mathcal{O}(\log N)\) 内精确算出 \(cand\) 在 \([L, R]\) 内的真实出现次数；
若真实频次 \(\ge threshold\) 则返回 \(cand\)，否则返回 \(-1\)。
总时间复杂度：单次在线查询严格 \(\mathcal{O}(\log N)\)，空间复杂度 \(\mathcal{O}(N)\)！

5. LeetCode 经典真题精选与深度精析¶

LeetCode 169 - 多数元素 (Majority Element) 简单
提示

绝对众数标准裸题。
- 题目明确保证数组中总存在多数元素（\(> \lfloor n/2 \rfloor\)）。
- 此时连第二阶段的验资都不需要，直接跑一遍标准单候选人投票，返回最终留存的 candidate 即可。时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(1)\)。
LeetCode 229 - 多数元素 II (Majority Element II) 中等
提示

\(k=3\) 广义摩尔投票标杆题。
- 寻找所有出现频次严格大于 \(\lfloor n/3 \rfloor\) 的元素。
- 由抽屉原理，合法元素至多只有 2 个。
- 维护 2 个候选人和 2 个计票器，集齐 3 个互不相同元素时同时抵消；第一阶段选出最多 2 个候选人后，必须在第二阶段再次遍历原数组验资，只将真实频次 \(> \lfloor n/3 \rfloor\) 的数加入答案。
LeetCode 1157 - 子数组中占绝大多数的元素 (Online Majority Element In Subarray) 困难
提示

线段树维护摩尔投票结合律 + 下标二分验资。
- 题目保证查询的门槛 \(threshold > (right - left + 1) / 2\)，即目标元素在子数组中必须是绝对众数。
- 线段树每个节点维护摩尔投票元组 \((candidate, weight)\)，利用合并算子在 \(\mathcal{O}(\log N)\) 时间内提取出区间合并后的唯一幸存候选人。
- 预处理哈希表保存每个元素出现的所有下标，在目标候选人的有序下标序列中用 upper_bound - lower_bound 在 \(\mathcal{O}(\log N)\) 内计算其在 \([left, right]\) 内部的实际出现次数。若达到 \(threshold\) 即输出，否则返回 \(-1\)。
洛谷 P2397 - yyy loves Maths VI (众数) 普及
提示

极限内存约束下的流式摩尔投票。
- 数据规模 \(N \le 2 \times 10^6\)，但内存限制只有极其苛刻的 4MB！
- 4MB 的内存甚至无法将全数组以 int 完整存入内存（\(2 \times 10^6 \times 4 \text{ Bytes} \approx 8 \text{MB}\)，直接超内存 MLE）。
- 题目保证存在绝对众数。此时必须利用摩尔投票的流式特性（Online Stream）：边用 cin / scanf 读入一个数，边与全局 candidate 和 count 抵消，完全不保存原数组，额外空间严格为 \(\mathcal{O}(1)\)。