Hash 的应用

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]区间。

无疑，这是一种在时间上更加高效的排序方法。

参考资料：计算机考研——机试指南[电子工业出版社]