统计数字

Description

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

Input

每组输入数据包含n+1行
第一行是整数n，表示自然数的个数
第2~n+1行，每行一个自然数。
1<=n<=200000，每个数均不超过1500000000（1.5*10^9)

Output

每组输出包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

Sample Input 1

8
2
4
2
4
5
100
2
100

Sample Output 1

2 3
4 2
5 1
100 2

解题思路：

（1）这道题只需将重复的数字记录下来，但是不能单纯的用一个int 数组记录，因为题目给数字最大可到达1500000000（1.5*10^9），所以数组会爆掉，没办法存那么大的数字，所以此题用一个map数组存，（map数组的底层是红黑树，具体可自己去了解知识）

（2）题目给的时间是2s    ，下面代码时间复杂度是n*logn；题目n最大200000，再乘以log200000，不超过题目给的时间，不会超时

（3）注意输出结果是从小到大输出，所以sort；

代码如下：

 1 #include<iostream>
 2 #include<map>
 3 #include<algorithm>
 4 using namespace std;
 5  
 6 map<int,int>mp;//用一个map数组记录，且不用将mp初始化为0，因为系统自动初始化为0；注意要头文件map
 7 map<int,int>vis;//用来记录
 8 int n ;
 9 long long int a[200005];
10 int main)
11 {
12     cin>>n; 
13    
14     forint i = 1 ; i <= n ;i++)
15     {
16          cin>>a[i];
17          mp[a[i]]++; //将重复的数字记录下来，计算一下相同的a[i]有几个；
18     }
19 
20     sorta,a+n);  //排序，注意要头文件  algorithm
21     forint i = 1;i <= n;i++)
22     {
23         ifmp[a[i]]!=0&&vis[a[i]]==0)   //如果mp[a[i]]！=0，且a[i]不相同，没被访问过
24         {
25             cout<<a[i]<<" "<<mp[a[i]];
26             cout<<endl;
27             vis[a[i]]=1;  //将输出的a[i]记录下来，记录它已访问过了；
28         }
29     }
30 
31     return 0; 
32 }