hrbust1164, 1287_____hrbust上的简单哈希

hrbust1164

Description

用计算机随机生成了N个0到910305（包含0和910305）之间的随机整数（N≤100000000），对于其中重复的数字，只保留一个，把其余相同的数去掉。然后再把这些数从小到大排序。

请你完成“去重”与“排序”的工作。

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

分析：

• 很简单的题目，直接定址法即可：

AC代码：

//author: svtter
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

#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 <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

#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了： 

但是很明显时间空间都过于大了。之前见过一个通过next数组来实现拉链法，遂同样如此写。。但是各种蛋疼，需要不停的检查删除，空间方面消耗达到惊人的59000K= =差一点就超，直接放弃了。

后来发现爽的解法，使用指针来写但不是动态开辟新空间的写法（奈何见识浅薄，今日才见）：

//author: svtter
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

#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;
}