题目描述

某次科研调查时得到了n个自然数，每个数均不超过$1.5×10^9$ 。

已知不相同的数不超过$10000$个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入格式

输入共n+1行。

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

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

输出格式

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

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

数据范围

$1≤n≤200000$

样例

输入样例：

8
2
4
2
4
5
100
2
100

输出样例：

2 3
4 2
5 1
100 2

算法1

(排序 + 双指针) $O(nlogn)$

我们将原数列从小到大排序，然后通过双指针扫描。指针i从小到大遍历，指针j从i开始，直到第一个a[j] != a[i]或j >= n时停止，计算该区间长度并输出即可。

时间复杂度

排序的复杂度为$O(nlogn)$，双指针扫描的复杂度为$O(n)$，所以总复杂度为为$O(nlogn)$。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N], n;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i ++)
    {
        int j = i;
        while (a[j] == a[i] && j < n) j ++;
        cout << a[i] << ' ' << j - i << endl;
        i = j - 1;
    }
}

算法2

(离散化) $O(nlogn)$

很明显可以用离散化来做——当我们想用一个count数组的下标存放数，数组的值存放数出现的个数时，就会发现下标的值域范围太大，但个数不多。此问题就可以用离散化解决。

然后就转化成了离散化板子题。

个人认为此题比算法基础课里的AcWing 802.区间和更纯粹，更适合新手上手离散化的板子。

时间复杂度

std::unique()的复杂度是$O(n)$，排序的复杂度是$O(nlogn)$，每次用find()查询的复杂度是$O(logn)$，总共查询$n$次，复杂度是$O(nlogn)$，所以总复杂度也是$O(nlogn)$。

C++ 代码

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> a, b, c;
int n, x;
int find(int x)
{
    int l = 0, r = a.size();
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> x;
        a.push_back(x);
        b.push_back(x);
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    c.resize(a.size());
    for (auto i : b) c[find(i)] ++;
    for (int i = 0; i < c.size(); i ++) 
        cout << a[i] << " " << c[i] << endl;
}

算法3

(std::unordered_map和std::set) $O(nlogn)$

直接使用STL自带的数据结构unordered_map和set其实就可以解决了。

unordered_map是一个哈希表，可以解决我们下标太大的问题。set保证其中所有元素只出现一遍且从小到大排列，可以直接帮助我们完成去重与排序的工作。

时间复杂度

unordered_map的插入复杂度都$O(1)$, 所以复杂度是$O(n)$。

set的查询复杂度为$O(logn)$，所以总复杂度为$O(nlogn)$。

C++ 代码

#include <set>
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
    unordered_map<int, int> a;
    set<int> b;
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        a[x]++;
        b.insert(x);
    }
    for (auto i = b.begin(); i != b.end(); i++) cout << *i << " " << a[*i] << endl;
}