题目描述

某次科研调查时得到了 n 个自然数，每个数均不超过 1.5×109。已知不相同的数不超过 104 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入格式

共 n+1 行。

第一行是整数 n，表示自然数的个数；

第 2 至 n+1 每行一个自然数。

输出格式

共 m 行（m 为 n 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出 2 个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

输入输出样例

输入 #1复制

8
2
4
2
4
5
100
2
100

输出 #1复制

2 3
4 2
5 1
100 2

说明/提示

• 30% 的数据满足：1≤n≤1000；
• 60% 的数据满足：1≤n≤50000；
• 100% 的数据满足：1≤n≤200000，每个数均不超过 1.5×109。

NOIP 2007 提高第一题

本题可使用 std::map 来存储每个自然数及其出现的次数。std::map 会自动按照键（即自然数）从小到大的顺序排序，我们只需遍历输入的自然数，统计每个数出现的次数，最后按顺序输出结果即可。

以下是实现该功能的 C++ 代码：

#include <iostream>
#include <map>

int main() {
    int n;
    // 读取自然数的个数
    std::cin >> n;

    // 使用 std::map 存储自然数及其出现的次数
    std::map<int, int> countMap;

    for (int i = 0; i < n; ++i) {
        int num;
        // 读取自然数
        std::cin >> num;
        // 对应自然数的计数加 1
        ++countMap[num];
    }

    // 遍历 map 并输出结果
    for (const auto& pair : countMap) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}

代码解释

1. 输入处理：首先读取自然数的个数 n，然后使用 for 循环读取 n 个自然数。
2. 统计次数：使用 std::map<int, int> countMap 来存储每个自然数及其出现的次数。对于读取到的每个自然数 num，使用 ++countMap[num] 对其计数加 1。
3. 输出结果：使用范围 for 循环遍历 countMap，pair.first 表示自然数，pair.second 表示该自然数出现的次数，按顺序输出即可。

复杂度分析

• 时间复杂度：插入操作的时间复杂度为 $O(\log m)$，其中 $m$ 是不相同数的个数，最多执行 $n$ 次插入操作，因此总的时间复杂度为 $O(n \log m)$。
• 空间复杂度：主要是 std::map 存储不相同数及其出现次数的空间开销，空间复杂度为 $O(m)$。