线性探测哈希表

题目描述

有一个长度为 m 的哈希表，桶下标为 0～m-1，初始时所有桶均为空。

哈希函数为：

h(x)=((x mod m)+m) mod m

现在按照输入顺序插入 n 个整数。发生冲突时使用线性探测：依次检查

h(x), (h(x)+1) mod m, (h(x)+2) mod m, ...

直到找到空桶。若关键字已经存在，则不重复插入。

题目保证不同关键字的数量不超过 m。

请输出插入完成后的整张哈希表。

输入格式

第一行两个整数 m、n。

第二行包含 n 个整数，表示按顺序插入的关键字。

输出格式

按下标 0～m-1 输出 m 个位置，位置之间用一个空格分隔：

• 桶中有关键字时输出该关键字；
• 桶为空时输出 EMPTY。

7 4
10 17 24 31

EMPTY EMPTY EMPTY 10 17 24 31

数据范围

• 1 <= m <= 200000
• 0 <= n <= 200000
• -10^9 <= x <= 10^9
• 不同关键字的数量不超过 m