[NOIP 2007 提高组] 统计数字

GitHub跳转原题关系图返回列表

先把所有数字排序，让相同数字连续出现，再线性扫描统计每个数字的出现次数。

OJ: luogu

题目 ID: P1097

难度:普及-

标签:排序枚举

日期: 2026-06-19 00:39

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定 n 个自然数。
要求统计每个不同数字出现的次数，并按数字从小到大的顺序输出。

思路

先看一个可以直接验证想法的朴素解：

边读边用 map 统计每个数字出现的次数，最后按键值从小到大输出。

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int n;
long long x;
map<long long, int> mp;

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

    for (map<long long, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
        cout << it->first << ' ' << it->second << '\n';
    }
}

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

    cin >> n;
    solve();

    return 0;
}

这个办法很直观，但本题还有一个更贴近“分组统计”的视角：

如果先把所有数字排序，那么：

  • 相同数字会排到一起
  • 数字本身也已经是从小到大排列

这样我们只要再扫一遍排序后的数组，就能把每一段相同数字压缩成：

数字值 出现次数

具体做法是：

  1. 先排序
  2. 维护当前数字 cur 和它的出现次数 cnt
  3. 当遇到新数字时，输出上一段的统计结果

代码

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

const int MAXN = 200005;

int n;
long long a[MAXN];

void solve() {
    sort(a + 1, a + n + 1);

    long long cur = a[1];
    int cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] == cur) {
            cnt++;
        }
        else {
            cout << cur << ' ' << cnt << '\n';
            cur = a[i];
            cnt = 1;
        }
    }
    cout << cur << ' ' << cnt << '\n';
}

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

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

    solve();

    return 0;
}

复杂度

时间复杂度是 O(nlogn)O(n log n)，空间复杂度是 O(n)O(n)。

总结

这题的关键不在“统计”本身，而在“按从小到大输出”。

排序以后，相同数字自然会聚成连续段，后面的统计就很顺手了。