利用hash进行排序输出

一时失言乱红尘 2022-05-31 23:54 172阅读 0赞

*  题目描述

给你 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>
    
    int main(int argc, const char * argv[]) {
        int hash[1000001] = {
       0};
        int n,m;
        while(scanf("%d", &n) != EOF){
            int x;
            scanf("%d", &m);
            for(int i = 0;i < n;i ++){
                scanf("%d", &x);
                hash[x + 500000] ++;
            }
            for(int j = 1000000;m > 0;j --){
                if(hash[j] != 0){
                    m --;
                    printf("%d",j - 500000);
                    if(m != 0) printf(" ");  //注意输出格式
                }
            }
            printf("\n");
        }
        return 0;
    }

*  总结

我们容易联想到，要输出前 m 大的数，我们只需将其降序排序，然后输出前 m 个数即可。那么，读者可能不禁会产生疑问，这不就是排序么，而这个问题我 们在本章第一节中不是已经讨论过了，为什么这里又再次提出来了。如果读者有 这个疑问，你就要反问自己了:你是否忽略了什么?我们在前几例中并没有着重 分析算法的复杂度，但这不代表复杂度分析在我们解题的过程中不那么重要，相 反复杂度分析是一个算法可行的前提与保证。即使本文没有明确的分析复杂度， 读者也要有自己估算复杂度的意识。在本例中，如果使用排序来解决该题，由于 待排序数字的数量十分庞大(1000000)，即使使用时间复杂度为 O(nlogn)的 快速排序，其时间复杂度也会达到千万数量级，而这在一秒时限内是不能被我们 所接受的，所以这里，我们并不能使用快速排序来解决本题。
      该代码介绍了一种在输入数据有如上所述的特点时，一种在时间上更加高效
    的排序方法。