1239：统计数字
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5×10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
【输入】
第一行是整数n，表示自然数的个数；
第2 n+1每行一个自然数。
【输出】
包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
【输入样例】
8
2
4
2
4
5
100
2
100
【输出样例】
2 3
4 2
5 1
100 2
【提示】
数据范围：
40%的数据满足：1≤n≤1000；
80%的数据满足：1≤n≤50000；
100%的数据满足：1≤n≤200000，每个数均不超过1500000000（1.5×10^9）。
本题目禁止使用STL及包含可以使用的相关调用。
1. #include <stdio.h> 2. #include <iostream> 3. #define N 1000001 4. using namespace std; 5. int t[N]; 6. void q_sort(int lf,int rt){ 7. int i=lf,j=rt,mid=t[(i+j)/2]; 8. while(i<=j){ 9. while(t[i]<mid)i++; 10. while(t[j]>mid)j--; 11. if(i<=j){ 12. swap(t[i],t[j]); 13. i++;j--; 14. } 15. } 16. if(i<rt) q_sort(i,rt); 17. if(lf<j) q_sort(lf,j); 18. } 19. int main(int argc, char *argv[]) 20. { 21. int n,i; 22. scanf("%d",&n); 23. for(i=1;i<=n;i++)scanf("%d",&t[i]); 24. q_sort(1,n); 25. i=1; 26. while(i<=n) 27. { 28. int s=t[i],k=i; 29. while(s==t[i]) i++; 30. printf("%d %d\n",t[i-1],i-k); 31. } 32. return 0; 33. }
