出现次数最多的数

形式化题目

给定 $n$ 个正整数，输出出现次数最多的那个数；若有多个数并列最多，输出其中最小的数。

关键不是只找一个最大出现次数，还要正确处理并列情况。数值范围为 $1$ 到 $10^4$ ，可以为每个数直接准备一个计数位置。

思路

先看一个可以直接验证想法的朴素解：枚举每个输入数，再扫描整个数组统计它出现了多少次。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:43
 */
// brute.cpp：小数据暴力解，逐个统计每个数在整个数组中出现了几次。
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    int a[1005];
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int answer = 1000000000;
    int best_count = 0;
    // 枚举候选数 a[i]，再扫描整个数组求它的出现次数。
    for (int i = 1; i <= n; i++) {
        int current_count = 0;
        for (int j = 1; j <= n; j++) {
            if (a[j] == a[i]) {
                current_count++;
            }
        }
        if (current_count > best_count ||
            (current_count == best_count && a[i] < answer)) {
            best_count = current_count;
            answer = a[i];
        }
    }

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

朴素解对每个候选数都重新统计一遍，时间复杂度为 $O(n^2)$ 。本题 $n \leqslant 1000$ 时它其实也能通过，但重复统计没有必要。

令 cnt[x] 表示数字 $x$ 出现的次数。读入每个数时执行 cnt[x]++，随后从 $1$ 到 $10^4$ 升序扫描：只在 cnt[value] 严格更大时更新答案。这样若两个数出现次数相同，较小的数先被记录，后面的较大数不会覆盖它。

计数扫描演示

下面用样例 $10, 1, 10, 20, 30, 20$ 展示计数与扫描过程：

步骤	操作	`cnt` 变化	当前最优
1	读入 10	`cnt[10]=1`	10（1 次）
2	读入 1	`cnt[1]=1`	1（1 次）
3	读入 10	`cnt[10]=2`	10（2 次）
4	读入 20	`cnt[20]=1`	10（2 次）
5	读入 30	`cnt[30]=1`	10（2 次）
6	读入 20	`cnt[20]=2`	10（2 次）

第 2 步中 1 和 10 出现次数相同，由于扫描从 1 开始且只在次数严格增加时更新，最终保留的是更小的 10。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:43
 */
#include <bits/stdc++.h>
using namespace std;

const int MAX_VALUE = 10000;

int n;
int cnt[MAX_VALUE + 1]; // cnt[x] 表示数字 x 出现的次数

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

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

    int answer = 0;
    int best_count = 0;
    // 从小到大扫描，出现次数相同时较小的数先被记录，保证答案最小。
    for (int value = 1; value <= MAX_VALUE; value++) {
        if (cnt[value] > best_count) {
            best_count = cnt[value];
            answer = value;
        }
    }

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

复杂度

朴素解的时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。

正式解的时间复杂度为 $O(n+V)$ ，其中 $V=10^4$ 是数值范围；空间复杂度为 $O(V)$ 。

总结

当值域较小时，计数数组可以把“反复统计同一件事”变成一次读入计数。并列最优的题目要特别决定扫描方向和更新条件：这里从小到大扫描，并且只在次数严格增加时更新，恰好保证答案最小。