[排序][哈希] 统计数字

本文主要是介绍[排序][哈希] 统计数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

Input

　　输入包含n+1行；
　　第一行是整数n，表示自然数的个数；
　　第2~n+1每行一个自然数。

Output

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

分析
哈希示范题啊
其实数据只用快速排序和朴素的O（N）寻找都行的。。哈希只是节省一丢丢的时间。
原版做法：
QS之后直接一条for下去，相同的相加，找到不同的时候输出，清零。。很水吧
然而hash就是很神奇的：
QS之前要把每个数进下哈希表然后储存同个数出现的次数。。然后排序的时候要排序一些神奇的东东（哈希表的下标）
最后输出。。很神奇的。

#include <iostream>
#include <cstdio>
using namespace std;
int n,i,x,a[243101],b[243101],p=243101,q,m,c[15001];
void qs(int l,int h)
{int i=l,j=h,mid=c[(l+h)/2],t;if (l>h) return;do{while (a[c[i]]<a[mid]) i++;while (a[c[j]]>a[mid]) j--;if (i<=j){t=c[i];c[i]=c[j];c[j]=t;i++;j--;}}while (i<=j);qs(i,h);qs(l,j);
}
int h(int d)
{return d%p;
}
int loc(int d)
{int q=h(d),i=0;while (a[(q+i)%p]!=2147483647&&a[(q+i)%p]!=d&&i<=p)i++;return q+i;
}
bool mem(int d)
{if (a[q]==d) return true;else return false;
}
void ins(int d)
{   if (a[q]==2147483647&&!mem(d)) {a[q]=d;m++;c[m]=q;}if (mem(d))b[q]++;return;
}
int main()
{scanf("%d",&n);for (i=1;i<=p;i++)a[i]=2147483647;for (i=1;i<=n;i++){scanf("%d",&x);q=loc(x);ins(x);}qs(1,m);for (i=1;i<=m;i++)printf("%d %d\n",a[c[i]],b[c[i]]);
}