Hash 的应用
@(算法)
注: 本文所讨论的 Hash 只讲诉其在机试试题解答中的应用。
题目描述：
给你 n 个整数，请按从大到小的顺序输出其中前 m 大的数
输入：
每组测试数据有两行，第一行有两个数 n，m（0<n,m<1000000），第二行包含 n 个各不相同，且都处于区间 [-500000,500000] 的整数
输出：
对每组测试数据按从大到小的顺序输出前 m 大的数
我们很容易会想到，用 sort()函数将其降序排序，然后输出前 m 大的数。多么简单的一道题啊，不禁让我感到疑惑，是否忽略了什么？在本题中，如果使用快排来解决该题，由于待排数字的数量十分庞大（1000000），根据快排的时间复杂度 O(nlogn)，其时间复杂度将会达到千万级。所以，我们并不能使用快速排序来解决本题。
代码块
#define OFFSET 500000
int 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] 区间。
无疑，这是一种在时间上更加高效的排序方法。参考资料：计算机考研——机试指南[电子工业出版社]