題目描述
某次科研調查時得到了n個自然數,每個數均不超過1500000000(1.5*109)。已知不相同的數不超過10000個,現在需要統計這些自然數各自出現的次數,並按照自然數從小到大的順序輸出統計結果。
題目輸入
多組輸入數據
每組數據包含n+1行:
第1行是整數n,表示自然數的個數。
第2~n+1行每行一個自然數。
題目輸出
每組數據輸出包含m行(m為n個自然數中不相同數的個數),按照自然數從小到大的順序輸出。每行輸出兩個整數,分別是自然數和該數出現的次數,其間用一個空格隔開。
樣例輸入
8
2
4
2
4
5
100
2
100
樣例輸出
2 3
4 2
5 1
100 2
解題思路
不用HASH的思路就是定義一個結構體,裡面有兩個參數,一是這個數的值,一是這個數出現的次數。然後開一個10000的結構體的數組,每讀到一個數,就從頭檢查是不是以前讀到過,如果讀到過就cnt++ 沒有讀到過就在最後面把它加上。
這個算法是對的 但是對於200000的數據O(n^2)顯然不行 所以要用HASH來優化數組的使用。思路是每次讀到一個數,就對它模一個與10000差不多的素數,然後用模完的值做下標(假設是t)。如果沒有數就直接放進去好了。如果發現s[t].num恰好就是讀到的數,那麼s[t].cnt++。如果發現這個位置被占了但s[t].num不是,就依次往後找到第一個沒有被占的,把其存到這裡。 這樣就完成了HASH對數組的優化使用。
最後把數組中所有有效的都整理一下,sort一下輸出即可。
詳見代碼
#include#include #include using namespace std; const int maxn = 10020; struct node { int num; int cnt; }; node s[maxn]; node temp[maxn]; bool cmp(node a,node b) { return a.num < b.num; } int main() { int n; while(scanf("%d",&n) != EOF) { for(int i = 1 ; i < maxn ; i ++) { s[i].num = -1; s[i].cnt = 1; } while(n--) { int a; scanf("%d",&a); int t = a%10009; while(1) { if(s[t].num == a) { s[t].cnt ++; break; } if(s[t].num == -1) { s[t].num = a; break; } t ++; } } int pt = 1; for(int i = 1 ; i < maxn ; i ++) { if(s[i].num != -1) { temp[pt].num = s[i].num; temp[pt++].cnt = s[i].cnt; } } sort(temp+1,temp+pt,cmp); for(int i = 1 ; i < pt ; i ++) { printf("%d %d\n",temp[i].num,temp[i].cnt); } } return 0; }