hash入门--直接定址

Problem Description

给你n个整数，请按从大到小的顺序输出其中前m大的数。

 

Input

每组测试数据有两行，第一行有两个数n,m(0各不相同，且都处于区间[-500000,500000]的整数。

 

Output

对每组测试数据按从大到小的顺序输出前m大的数。

 

Sample Input

5 3 3 -35 92 213 -644

Sample Output

213 92 3

链接：

 

最简单的哈希，空间换时间！！！ 156MS

直接定址法

具体思路：数据量大，数据在一定范围；

hash表（将数据直接映射到地址，这里给了范围[-500000,500000]可以直接定址）

#include<stdio.h>
#include<string.h>
#define Max 1000000+10
int hash[Max];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(hash,0,sizeof(hash));
        int temp;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&temp);
            hash[500000+temp]=1;//直接定址法ax+b,a b是常数
        }
        int count=0;
        for(int j=Max;j>=0;j--)//从大到小
        {
            if(hash[j]==1)
            {
                count++;

                if(count<m)
                    printf("%d ",j-500000);
                else if(count==m)
                    printf("%d\n",j-500000);
                else
                    break;
            }
        }
    }
    return 0;
}