洛谷B3639众数问题详解：排序、哈希与摩尔投票的选型指南

洛谷B3639这道题，我是被群里的新人问过之后才仔细去看的。说句实话，题面没有任何弯弯绕，就是给你一个长度为 n 的数列，让你把出现次数最多的那个数找出来。但正因为看起来简单，它反而是新手翻车的高发区：有人没看清输出规则，有人不看数据范围直接开大数组，有人把"众数"和"多数元素"当成一回事，最后在小测试点上栽了跟头。

如果你正在刷洛谷的基础题单，或者刚学完数组想找点题练手，这篇应该正好对得上。我会从审题开始，把这类"序列统计"题的几种主流解法都过一遍：排序扫描、哈希计数，以及经常被误用的摩尔投票。不只是给代码，还会讲清楚每种解法在什么数据下能用、什么情况下会挂、提交时有哪些隐藏的坑。

1. 审题是第一关：众数、多数元素和输出规则别搞混

1.1 两种"众数"定义，做题前先分清

我见过很多WA不是代码写错，而是题目理解错。B3639这类题，题面里如果写的是"求众数"，那大多数情况下指的是出现次数最多的数；但OJ里的"众数"偶尔会被理解成"出现次数超过一半的数"，国外教材管这个叫 majority element，中文有时也翻译成众数。这两种问法，解法完全不同，写错方向基本就是白费功夫。

如果题目要的是"出现次数最多的数"，那需要考虑的可能不止一个答案：比如序列 1 1 2 2，1 和 2 都出现了两次，这就是并列众数。题面必须规定清楚输出哪一个，常见的有三种：输出数值最小的、输出任意一个、输出最先达到最大出现次数的。这个细节直接决定你的代码比较条件怎么写。

如果题目要的是"出现次数超过一半的数"，那事情就简单多了：这样的数最多只能有一个，因为两个不同的数不可能同时超过 n/2。它的难点在于"可能不存在"，所以很多题会要求你判断是否存在，不存在时要输出某个特定值（比如 -1 或者"no"）。

我的建议是：拿到题先别急着敲键盘，把样例在草稿纸上手动推一遍，看看它到底要的是哪种"众数"，再决定解法。你去翻B3639的题解区，会发现有人用哈希、有人用排序、有人用摩尔投票，第一反应别慌，先想想他们分别对应的是哪种题意。能把这点分清，这道题你已经做对了一半。

1.2 数据范围决定你用什么级别算法

做题第一步不是找最优解，而是确定"当前约束下哪些算法能过、哪些会超时"。B3639如果没有特殊说明，n 一般不会太小，但不同版本的题目约束可能差很多，所以看数据范围这个习惯必须养成。

我整理了一个选型参考表，按 n 的大小和值域范围来选：

举个例子：如果 n ≤ 10^5，数值范围在 10^9 以内，排序 O(n log n) 和哈希 O(n) 都能轻松过；如果 n 放大到 10^7，排序很可能超时，哈希内存也可能爆，这时候就必须找 O(n) 且空间小的办法；如果值域很小，比如数字只在 0 到 10^6 之间，那开一个计数数组比什么哈希都快，常数小得多，写起来也简单。

这里有个常见的认知偏差：总以为 O(n) 一定比 O(n log n) 快。实际在数据量 10^6 左右时，sort 的常数非常小，很多时候排序法比 unordered_map 还快，因为哈希表的插入和内存分配开销很大。所以"能过题"永远比"理论复杂度最优"更重要。

2. 先排序再扫描：新手最不容易写错的解法

2.1 思路和代码模板

排序法的核心思想很简单：把数组排好序后，相同的数字一定紧挨在一起。接下来只需要从左往右扫一遍，维护"当前连续相同段的长度"，同时记录全局最长的那段对应的值，就是答案。

这个思路最大的优势是正确性非常直观，不依赖任何复杂的数据结构，只需要你写过 sort。我建议新手第一次做这类题，优先用这个方法，先把题目跑通，再考虑优化。

cpp复制#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a.begin(), a.end());

    int ans = a[0], best = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (i > 0 && a[i] == a[i - 1]) {
            cnt++;
        } else {
            cnt = 1;
        }
        if (cnt > best) {
            best = cnt;
            ans = a[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

注意两个细节：一是 cnt 在一段新的连续数字开始时重置为 1，而不是 0；二是 cnt > best 这个条件，如果你要求并列时输出数值最小的，因为排序后小的在前，只有当 cnt 严格大于 best 时才更新答案，这样第一个达到最大出现次数的小值会被保留。如果题面要求输出最大的那个，就要把条件改成 cnt >= best。这种"差一个符号就WA"的细节，恰恰是很多人丢分的原因。

2.2 排序法为什么不容易错，又输在哪

排序法不容易错，因为它把"统计频次"的问题转化成了"扫描有序数组"的问题，每一步都看得见摸得着。调试的时候你甚至可以把排序后的数组打印出来，肉眼检查自己哪里数错了。空间上它是原地排序，几乎不占额外内存，这在内存限制严格的题目里是很大的优势。

但它也有天花板。首先复杂度是 O(n log n)，当 n 到 10^7 级别时，排序时间会非常可观，大概率被卡超时。其次，如果题目要求输出的是"所有众数"或者需要按出现次数从高到低输出，排序法虽然能做，但要额外处理分组，代码会变长，不如哈希表直接。

我本地实测过一组 10^6 个随机 int 的排序，大约 0.3 秒左右，在洛谷上一般不会超时。但同样一组数据，如果用 unordered_map 做哈希计数，反而可能到 1 秒以上。这就是为什么我一直强调：别迷信理论复杂度，常数也很关键。排序法的定位是"稳"，它是你手里最不容易出错的底牌。

3. 哈希表计数：实际刷题中用得最多的写法

3.1 边读边更新的陷阱与标准写法

哈希表计数的思路更符合人的直觉：遍历一遍数列，用每个数当 key，出现次数当 value，最后找出 value 最大的 key。在 C++ 里对应 unordered_map<int, int>，Java 里是 HashMap<Integer, Integer>，Python 里是 dict。

很多新手会写一个"优化版"：一边读入一边更新答案，省得最后再遍历一遍。但这个优化很容易踩坑，尤其是题面要求"有多个众数时输出较小的"这种规则时。看这个例子：序列 5 3 3 5，1 和 3 都出现两次。如果题面要求输出较小的众数，答案应该是 3。但边读边更新的代码读到最后一个 5 时，发现 5 的计数也达到了 2，和当前 best 相等，这时如果更新逻辑没写好，就会把答案从 3 改成 5，直接 WA。

正确做法是分成两步：第一遍遍历所有数，只负责统计每个数出现的次数；第二遍再遍历哈希表，找出满足条件的答案。这样无论题面要求怎样的平手规则，你都可以在第二遍的 if 条件里显式处理。

cpp复制#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    int ans = 0, best = -1;
    for (auto &p : cnt) {
        if (p.second > best) {
            best = p.second;
            ans = p.first;
        }
    }
    cout << ans << '\n';
    return 0;
}

这段代码里我把 best 初始化为 -1，这样即使所有数都只出现一次，也能正常更新答案。如果题目要求并列时输出较小的数，把第二个循环里的判断改成 if (p.second > best || (p.second == best && p.first < ans)) 即可。这个"先统计、再查找"的模式非常通用，后面很多字符串、矩阵统计题都能复用。

3.2 unordered_map 的遍历和平手处理

C++ 的 unordered_map 遍历顺序是未定义的，底层哈希表决定了它的迭代顺序和插入顺序、数值大小都没有必然关系。所以一旦题面存在"并列时输出某个特定值"的规则，你不能依赖哈希表的遍历顺序，必须在循环里做显式比较。

如果你用的是 map<int, int>，情况会好一些，因为 map 底层是红黑树，遍历时按键从小到大排列。但代价是每次插入多一个 O(log n)，当 n 到 10^6 时，map 往往比 unordered_map 慢不少。我的建议是：能用 unordered_map 就用 unordered_map，平手规则靠显式比较解决，不要为了省事用 map，除非 n 很小。

另外提醒一句，Java 的 HashMap 和 Python 的 dict 也存在类似问题。Python 3.7 之后 dict 保持插入顺序，但做题时别依赖这个特性，因为你的插入顺序和"数值大小""第一次出现位置"之间的关系，在不同写法下可能完全不同。写显式比较条件，是最稳妥的做法。

3.3 时间与内存的真实情况

unordered_map 平均插入和查找是 O(1)，但这个 O(1) 常数非常大。每个元素不仅要存 key 和 value，还要存哈希值、桶指针等额外信息，内存开销通常是普通数组的十倍以上。一次插入可能要触发多次内存分配、哈希计算，甚至哈希冲突时的链表遍历。

我粗略估算过一个场景：往 unordered_map 里塞 10^6 个 int，每个节点大约几十字节，总内存可能到几十 MB 甚至上百 MB。如果洛谷的内存限制是 128MB，而你的代码还有其他容器，极有可能在极端数据下被 MLE。所以我在 1.2 里才强调，值域小的时候优先用计数数组，那个才是真正的 O(n) 时间和 O(U) 空间，常数小得离谱。

还有一点，C++ 的 unordered_map 在某些构造的恶意数据下会退化成 O(n) 复杂度，虽然洛谷一般不卡这个，但你如果给 unordered_map 指定自定义哈希函数，或者干脆用 map，都能规避。实战中我更倾向于：能用 vector 计数就不用哈希，必须用哈希时提前算好内存够不够。

4. 摩尔投票法：只针对"超过一半"场景的 O(n) 空间最优解

4.1 抵消思想是怎么来的

摩尔投票法（Boyer-Moore Majority Vote Algorithm）解决的是另一个问题：在数组中寻找出现次数超过 n/2 的数。它的核心思想可以理解成"不同数字两两抵消"。

想象数组里每个数都是一名士兵，它们的任务是让自己代表的数字活到最后。遍历时，我们手上维护一个候选者 candidate 和一个计数器 count。当 count 为 0 时，把当前数字设为候选者，count 置 1；接下来如果遇到和 candidate 相同的数，count 加 1，遇到不同的数，count 减 1。这个过程相当于"一个候选者士兵遇到一个不同阵营的士兵，两人同归于尽"。

为什么这能找出超过一半的数？因为如果某个数真的出现了 n/2 以上，它比其他所有数加起来还要多。无论怎么配对抵消，最后一定会有这个数的士兵剩下。反过来，如果不存在这样的多数元素，最后剩下的 candidate 没有任何保证，它可能只是一个"幸存者"而已，所以必须二次验证。这个方法的精妙之处在于，它用 O(n) 时间、O(1) 空间就完成了任务，不需要额外的哈希表。

4.2 代码和二次验证

摩尔的代码极其简短，但正因为短，很多人细节写错。标准写法是下面这样，我把验证部分也写进去了：

cpp复制#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int candidate = 0, count = 0;
    for (int x : a) {
        if (count == 0) candidate = x;
        count += (x == candidate) ? 1 : -1;
    }

    // 验证 candidate 是否真的超过一半
    int total = 0;
    for (int x : a) {
        if (x == candidate) total++;
    }

    if (total > n / 2) cout << candidate << '\n';
    else cout << "no" << '\n';

    return 0;
}

注意，如果题面保证一定存在多数元素，验证部分可以删掉；但如果没说保证，就绝不能省。一组 1 2 3 4 5 的数据没有任何多数元素，你直接输出 candidate，大概率是错的。这个坑太常见了，我见过好几个熟手在快速写摩尔投票时都栽过。

4.3 摩尔投票在 B3639 这类题里能不能用

这是关键问题。如果题面要的是"出现次数最多的数"（普通众数），摩尔投票不能直接套用。举个反例：序列 1 2 2 3 3，出现次数最多的是 2 和 3，各两次，但没有任何数超过一半。摩尔投票跑完之后得到的 candidate 可能是 3，也可能是 1，完全取决于数组顺序，但它无法告诉你"出现次数最多"这个问题的正确答案。

所以结论很简单：只有在你确定题面问的是"是否存在超过一半的数"时，才用摩尔投票。如果你发现 B3639 的官方题解里有摩尔投票的写法，那说明那版题面要的是多数元素；如果题解里大多是排序或哈希，那要的就是普通众数。这两种题解在同一道题下同时出现，往往是题目版本或翻译差异导致的，也正好对应我在第 1 章强调的审题问题。

5. 提交记录里的坑：快读、边界样例与解法选型

5.1 打开同步流的 cin，和快读的差距

很多新手在数据量大的题里用 cin/cout 超时，第一反应是"算法不够快"，其实有时候算法完全没问题，纯粹是 IO 拖了后腿。C++ 的 cin/cout 默认要和 C 的 stdio 同步，每次输入输出都要检查缓冲区状态，这开销非常大。

刷题时我习惯在 main 函数开头写上这两行：

cpp复制ios::sync_with_stdio(false);
cin.tie(nullptr);

第一行关闭 cin/cout 和 stdio 的同步，第二行取消 cin 和 cout 之间的绑定，避免每次输出都强制刷新缓冲区。写完这两行，cin/cout 的速度能接近 scanf/printf。如果输入量特别大，比如 n 到 10^6 以上，我还会直接手写快读，原理就是自己用 getchar 读取字符并拼成整数：

cpp复制int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

我本地粗略测过，n = 10^6 时，不开同步的 cin 可能 1 秒多甚至更慢，关了同步能压到几百毫秒，手写快读则更快一些。虽然洛谷很多题卡得没那么狠，但养成这个习惯，遇到大数据量题不会吃亏。

5.2 必须自己构造的边界样例

在提交之前，我建议你手动构造几个特殊的样例，先在本地跑一遍。以下这几个情况，是我看题解评论区出现频率最高的 WA 来源：

• n = 1：只能输出唯一那个数，很多循环逻辑没处理好的代码在这里就崩了。
• 所有数完全相同：比如 7 7 7，答案就是 7，注意 cnt 的累计逻辑。
• 两个数并列最多：比如 5 5 1 1，你要确认题面让输出 5 还是 1，代码条件是否对应。
• 负数：如果数据范围包含负数，计数数组就不能直接用了，哈希和排序不受影响。
• 全部数都只出现一次：此时"出现次数最多"不唯一，输出规则直接决定结果。

这些样例几乎不花时间，但能帮你提前暴露逻辑错误。刷题不是比谁提交次数多，省下 WA 的时间去学习新的知识点，性价比高得多。

5.3 三种解法实测对比

我把前面几种方法在同一组数据下的体感表现整理成了表格。注意这不是官方基准测试，只是给个直观印象：

实际选型时，我的决策顺序是这样的：

1. 确认题面要的是哪种"众数"，以及并列时输出哪个；
2. 看 n 和值域范围，排除明显不可行的方法；
3. 在可行的方法里选最好写的那个，先保证 AC；
4. 只有 AC 之后，才考虑要不要优化成更酷的解法。

大部分情况下，排序法或哈希法足够通过 B3639，摩尔投票的价值在于"你知道有这么一个更优解"，是一种知识储备，而不是每道题都必须拿出来用。

5.4 如果这是我自己的做题顺序

我会先花两分钟把样例在纸上推一遍，确认输出规则，再按数据范围选方法：n 在 10^5 以内直接排序，思路清晰不易错；n 更大且值域大，考虑 unordered_map；如果是明确的"超过一半"场景，直接摩尔投票。写完后用 5.2 里的边界样例本地自测一遍，再提交。

刷这类基础题，最大的收获不是背下某个解法，而是养成"先审题、再选型、后写码"的习惯。等你刷多了就会发现，很多题目表面上不一样，底层的统计逻辑是相通的，拿到手的解法换一层皮就能用。B3639 就是这样一个很好的练手点，把它的几种思路吃透，后面遇到频率统计类的问题，你会比别人少走很多弯路。