NOJ1601 數次統計 哈希簡單應用

NOJ1601 數次統計 哈希簡單應用

題目描述

某次科研調查時得到了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;
}