Hash 的应用

Hash 的应用@(算法)注:本文所讨论的Hash只讲诉其在机试试题解答中的应用。题目描述：给你n个整数，请按从大到小的顺序输出其中前m大的数输入：每组测试数据有两行，第一行有两个数n，m（0<n,m<1000000），第二行包含n个各不相同，且都处于区间[-500000,500000]的整数输出：对每组测试数据按从大到小的顺序输出前m大的数我们很容易会想到，用sort()函数将其降序排序，然后输出前m大的数。多么简单的一道题啊，不禁让我感到疑惑，是否忽略了什么？在本题中，如果使用快排来解决该题，由于待排数字的数量十分庞大（1000000），根据快排的时间复杂度O(nlogn) ，其时间复杂度将会达到千万级。所以，我们并不能使用快速排序来解决本题。代码块#define OFFSET 500000int hash[1000000];int main() { int n, m; while (scanf("%d%d",&n,&m)!=EOF &&n!=0) { for (int i = -500000; i <= 500000; i++) { hash[i + OFFSET] = 0; } for (int i = 0; i < n; i++) { int x; scanf("%d", &x); hash[x + OFFSET]=1; } for (int i = 1000000; i >= m+OFFSET; i–) { if (hash[i]==1) { printf("%d “, i - OFFSET); } } } return 0;}代码解读#define OFFSET 500000 由于输入数据出现负数，于是我们不能直接把输入数据当做数组下标来访问数组元素，而是将每一个输入的数组都加上一个固定的偏移量，使输入数据的[-500000,500000]区间被映射到数组下标的[0,1000000]区间。无疑，这是一种在时间上更加高效的排序方法。参考资料：计算机考研——机试指南[电子工业出版社]