程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hrbust1164, 1287_____hrbust上的簡單哈希

hrbust1164, 1287_____hrbust上的簡單哈希

編輯：C++入門知識

hrbust1164, 1287_____hrbust上的簡單哈希

hrbust1164

Description

用計算機隨機生成了N個0到910305（包含0和910305）之間的隨機整數（N≤100000000），對於其中重復的數字，只保留一個，把其余相同的數去掉。然後再把這些數從小到大排序。

請你完成“去重”與“排序”的工作。

Input

輸入有2行，第1行為1個正整數，表示所生成的隨機數的個數：

第2行有N個用空格隔開的正整數，為所產生的隨機數。

Output

輸出也是2行，第1行為1個正整數M，表示不相同的隨機數的個數。第2行為M個用空格隔開的正整數，為從小到大排好序的不相同的隨機數。

Sample

Sample Input

10
20 40 32 67 40 20 89 300 400 15
Sample Output
8
15 20 32 40 67 89 300 400

分析：

AC代碼：

//author: svtter
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define INF 0xffffff
#define lln long long

#ifdef ONLINE_JUDGE
#define FOI(file) 0
#define FOW(file) 0
#else
#define FOI(file) freopen(file,"r",stdin);
#define FOW(file) freopen(file,"w",stdout);
#endif

using namespace std;

#define N 910305 
bool num[N];

int main()
{
    //FOI("input");
    //FOW("output");
    //write your programme here

    int i, n;
    int t, sum;
    int c;
    while(~scanf("%d", &n))
    {
        memset(num, 0, sizeof(num));
        sum = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &t);
            if(num[t] == 0)
            {
                sum++;
                num[t] = 1;
            }
        }
        printf("%d\n", sum);
        c = 0;
        for(i = 0; i < N; i++)
        {
            if(num[i])
            {
                if(c != sum-1)
                {
                    printf("%d ",i);
                    c++;
                }
                else
                {
                    printf("%d\n", i);
                    break;
                }
            }
        }
    }
    return 0;
}

hrbust1287

Description

用計算機隨機生成了N個0到1000000000（包含0和1000000000）之間的隨機整數（N≤5000000），對於其中重復的數字，只保留一個，把其余相同的數去掉。然後再把這些數從小到大排序。請你完成“去重”與“排序”的工作

Input

輸入有2行，第1行為1個正整數，表示所生成的隨機數的個數： N 第2行有N個用空格隔開的正整數，為所產生的隨機數。

Output

輸出也是2行，第1行為1個正整數M，表示不相同的隨機數的個數。第2行為M個用空格隔開的正整數，為從小到大排好序的不相同的隨機數。

Sample

Sample Input
10
20 40 32 67 40 20 89 300 400 15
Sample Output
8
15 20 32 40 67 89 300 400

算法分析：

這道題目一開始想都沒想就用了直接定址，爽爽的WA了。隨後開始寫拉鏈法的同時又想到一個新的算法，基本上等於暴力解了：

就是開兩個數組，一個排好序，重復的就不放在裡面了。

AC代碼:

//author: svtter
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define INF 0xffffff
#define lln long long

#ifdef ONLINE_JUDGE
#define FOI(file) 0
#define FOW(file) 0
#else
#define FOI(file) freopen(file,"r",stdin);
#define FOW(file) freopen(file,"w",stdout);
#endif

using namespace std;

#define N 5000003
int num[N];
int num2[N];

int main()
{
    //FOI("input");
    //FOW("output");
    //write your programme here

    int i, j, n;
    int sum;
    while(~scanf("%d", &n))
    {
        memset(num2, -1, sizeof(num2));
        sum = n;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &num[i]);
        }
        sort(num, num+n);
        num2[0] = num[0];
        j = 0;
        for(i = 1 ; i < n; i++)
        {
            if(num[i] != num2[j])
                num2[++j] = num[i];
            else
                sum--;
        }

        printf("%d\n", sum);
        for(i = 0; i < sum-1; i++)
            printf("%d ", num2[i]);
        printf("%d\n", num2[sum-1]);
    }
    return 0;
}

爽爽的AC了： AC圖片

但是很明顯時間空間都過於大了。之前見過一個通過next數組來實現拉鏈法，遂同樣如此寫。。但是各種蛋疼，需要不停的檢查刪除，空間方面消耗達到驚人的59000K= =差一點就超，直接放棄了。

後來發現爽的解法，使用指針來寫但不是動態開辟新空間的寫法（奈何見識淺薄，今日才見）：

//author: svtter
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define INF 0xffffff
#define lln long long

#ifdef ONLINE_JUDGE
#define FOI(file) 0
#define FOW(file) 0
#else
#define FOI(file) freopen(file,"r",stdin);
#define FOW(file) freopen(file,"w",stdout);
#endif

using namespace std;

const int MP = 1007;
struct Node
{
    int d;
    Node *next;
};


Node *pnd[MP+1];
Node nd[MP+1];
int n_cnt;
int a_cnt;
int a[MP+10];


int main()
{
    //FOI("input");
    //FOW("output");
    //write your programme here

    int i, d, n;
    int p;
    Node *pt;
    bool found;
    while(~scanf("%d", &n))
    { 
        memset(pnd, 0, sizeof(pnd));
        n_cnt = 0;
        a_cnt = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &d);
            p = d % MP;
            found = false;
            pt = pnd[p];
            while(pt)
            {
                if(pt->d == d)
                {
                    found = 1;
                    break;
                }
                pt = pt->next;
            }
            if(!found)
            {
                nd[n_cnt].d = d;
                nd[n_cnt].next = pnd[p];
                pnd[p] = &nd[n_cnt];
                n_cnt++;
                a[a_cnt++] = d;
            }
        }
        sort(a ,a+a_cnt);
        printf("%d\n", a_cnt);
        for(i = 0; i < a_cnt-1; i++)
            printf("%d ", a[i]);
        printf("%d\n", a[a_cnt-1]);
    }
    return 0;
}