HASH的应用（负数下标用偏移量解决）

Input

每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个处于区间[-500000,500000]的整数。

Output

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

Sample Input

5 3
3 -35 92 213 -644

Sample Output

213 92 3

解题思路

1 数据量大，使用排序1秒不能解决，因为数字的范围达到百万级 ，时间复杂度达到千万数量级，必须用哈希,

2 哈希针对的是输入数值处于特定范围的问题，建立一个范围大小的数组，建立hash[x] = x出现多少次的映射 

3 对于定义较大容量的数组，放在函数体外，这样用全局变量，内存会比较充足 

4 对于区间为负的，需要设定下标补偿值

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define OFFSET 500000

int Hash[1000001];

int main()
{
    int n,m;
    int i;
    int temp;

    while( scanf("%d%d",&n,&m)!=EOF){
        for( i=-500000; i<=500000; i++){
            //初始化，将每个数字都标记为未出现
            Hash[i+OFFSET] = 0;
        }
        for( i=1; i<=n; i++){
            scanf("%d",&temp);
            Hash[temp+OFFSET] += 1;
        }

        for( i=500000; i>=-500000; i--){
            while( Hash[i+OFFSET]){
                printf("%d",i);
                m--;
                Hash[i+OFFSET]--;
                if( m ) printf(" ");
                else break;
            }
            if( m==0 ) break;
        }
    }

    return 0;
}