题面：

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

样例输入：

8242451002100

样例输出：

2 34 25 1100 2

数据范围：N <= 200000

 

这个题因为数据范围很小，所以是一道水题，直接用sort就可以水过。时间复杂度O(nlogn)。

代码：

 

#include 
     
      #include 
      
       int data[200010];#define gi(a) do {                             \  register char ch;                         \  while((a = getchar()) > '9' || a < '0');         \  for(a -= '0'; (ch = getchar()) >= '0' && ch <= '9'; a = a*10+ch-'0'); \} while(0) int main() {  register int i, cnt = 0, N;  gi(N);  for(i = 1; i <= N; i++)    gi(data[i]);  std::sort(data+1, data+1+N);   for(i = 1; i <= N; i++) {    cnt++;     if(data[i] != data[i+1]) {      printf("%d %d\n", data[i], cnt);      cnt = 0;    }  }}
      
     

实测144ms

但是如果数据卡sort（这个题数据良心不卡sort），或者N的范围更大，那么我们就要想想更好的算法了。

因为数字是固定不变的，我们首先可以想到一个很常规的算法：

开很多个桶，如果数字a出现了一次，那么桶a就++，最后把桶扫一遍。

但是如果数字太大，那么开很多个桶就会很浪费空间，甚至爆内存。

可以再开一个哈希表优化：

首先扫一遍，把值放进哈希表里，记录++。

然后把哈希表里面记录的数据扫一遍，排序输出。

设不重复的数字为m个，可见m <= n

时间复杂度O(mlogm+n*k)，k取决于哈希函数的优劣（人品）

代码如下：

 

#include 
     
      #include 
      
       #define MAXN 200010#define gi(a) do {                             \  register char ch;                         \  while((a = getchar()) > '9' || a < '0');         \  for(a -= '0'; (ch = getchar()) >= '0' && ch <= '9'; a = a*10+ch-'0'); \} while(0)struct number {  int num, cnt;};number vis[MAXN]; number array[MAXN];inline bool comp(const number &a, const number &b) {  return a.num < b.num; }inline void hash(const int &a) {  int key = a%MAXN;  while(vis[key].cnt && vis[key].num != a) key++;  if(vis[key].cnt == 0) vis[key].num = a;   vis[key].cnt++;}int main() {  int N, tot = 0, a, i, j;  gi(N);   for(i = 1; i <= N; i++) {    gi(a);    hash(a);  }  for(i = 0; i <= MAXN-1; i++)    if(vis[i].cnt)      array[++tot] = vis[i];  std::sort(array+1, array+tot+1, comp);  for(i = 1; i <= tot; i++)     printf("%d %d\n", array[i].num, array[i].cnt);  return 0;}
      
     

实测64ms

（其实就这两个代码速度在所有代码中都是最快的，无论是不是加了优化）