Hash 的应用

c/c++

浏览数:168

2019-3-29

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

无疑,这是一种在时间上更加高效的排序方法。
参考资料:计算机考研——机试指南[电子工业出版社]