【算法训练】Hash的应用

Hash的应用当数据较为庞大，但是数据的数量是有限范围内的，各不相同的。

例题
题目描述

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

输入

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

输出

对每组测试数据按从大到小的顺序输出前m大的数样例输入
5 3
3 -35 92 213 -644

样例输出

213 92 3

#include<stdio.h>
#define OFFSET 500000 //偏移量，用于补偿实际数字与数组下标之间的偏移
int Hash[1000001];//hash数组，记录每个数字是否出现，不出现为0，出现后标记为1
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=-500000;i<=500000;i++){
            Hash[i+OFFSET]=0;
        }//初始化，将所有数字都标注为未出现 
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            Hash[x+OFFSET]=1;//凡是出现过的数字，改数组元素被标记为1 
        }
        for(int i=500000;i>=-500000;i--){
            if(Hash[i+OFFSET]==1){//判断该数字是否输入 
                printf("%d",i);//输出该数字 
                m--;//输出一个数字，m减一
                if(m!=0){
                    printf(" ");
                } else{
                    printf("\n");
                    break;//当前m个数字都已经输出完成，则跳出遍历循环 
                }
            }
        } 
    }
    
    return 0; 
}

该例题面限定了输入的数字一定是[-500000,500000]区间里 的整数，且各不相同。若利用一个数组分别统计每一种数字是否出现，其空间复 杂度依旧在题目的限定范围内。且统计出现数字当中较大的 m 个数字，也仅需 要从尾至头遍历这个数组，其时间复杂度仍在百万数量级.