问题 O: 进阶实验8-2.1:逆散列问题

内存限制:64 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:22 解决:19

题目描述

给定长度为 N 的散列表,处理整数最常用的散列映射是 ()=%N。如果我们决定用线性探测解决冲突问题,则给定一个顺序输入的整数序列后,我们可以很容易得到这些整数在散列表中的分布。例如我们将 1、2、3 顺序插入长度为 3 的散列表HT[]后,将得到HT[0]=3,HT[1]=1,HT[2]=2的结果。

但是现在要求解决的是“逆散列问题”,即给定整数在散列表中的分布,问这些整数是按什么顺序插入的?

输入

输入的第一行是正整数 N(1000),为散列表的长度。第二行给出了 N 个整数,其间用空格分隔,每个整数在序列中的位置(第一个数位置为0)即是其在散列表中的位置,其中负数表示表中该位置没有元素。题目保证表中的非负整数是各不相同的。

输出

按照插入的顺序输出这些整数,其间用空格分隔,行首尾不能有多余的空格。注意:对应同一种分布结果,插入顺序有可能不唯一。例如按照顺序 3、2、1 插入长度为 3 的散列表,我们会得到跟 1、2、3 顺序插入一样的结果。在此规定:当前的插入有多种选择时,必须选择最小的数字,这样就保证了最终输出结果的唯一性。

样例输入 复制

11
33 1 13 12 34 38 27 22 32 -1 21

样例输出 复制

1 13 12 21 33 34 38 27 22 32

来源/分类