[Hash]統計
904 ワード
テーマの大意
n個の数が与えられ、各数は1.5*109を超えず、これらの数のそれぞれの出現回数を統計し、統計結果を小さい順に出力する.
テーマ解析
データ規模は1.5*109なのでハッシュキー自体がアドレスとして爆発します
したがって,ハッシュテーブルを用いてあるSが出現するか否かを記録するほかに出現回数を記録することを考えるので,1つの2次元配列を用いて出現回数を格納すればよい.
終了後、ハッシュテーブルの数を新しい配列に配置し、ソートして出力します.
n個の数が与えられ、各数は1.5*109を超えず、これらの数のそれぞれの出現回数を統計し、統計結果を小さい順に出力する.
テーマ解析
データ規模は1.5*109なのでハッシュキー自体がアドレスとして爆発します
したがって,ハッシュテーブルを用いてあるSが出現するか否かを記録するほかに出現回数を記録することを考えるので,1つの2次元配列を用いて出現回数を格納すればよい.
終了後、ハッシュテーブルの数を新しい配列に配置し、ソートして出力します.
#include
#include
#include
#define h(x) x%p
#define p 1000007//
using namespace std;
struct A
{
int x,n;
}ans[p];
int n,x,a[p][2],num;
//a[x][0] x S ,a[x][2] S
int loc(int x)
{
int k=h(x),i=0;
while(a[(k+i)%p][0]!=0&&a[(k+i)%p][0]!=x)
i++;
return (k+i)%p;
}//
bool cmp(A a,A b)
{
return a.x0)
{
ans[++num].x=a[i][0];
ans[num].n=a[i][1];
}
sort(ans+1,ans+1+num,cmp);//
for(int i=1;i<=num;i++)
cout<