Hashing - Hard Version
Given a hash table of size N, we can define a hash function H(x)=x%N. Suppose that the linear probing is used to solve collisions, we can easily obtain the status of the hash table with a given sequence of input numbers.
However, now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices, the smallest number is always taken.
Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), which is the size of the hash table. The next line contains N integers, separated by a space. A negative integer represents an empty cell in the hash table. It is guaranteed that all the non-negative integers are distinct in the table.
Output Specification:
For each test case, print a line that contains the input sequence, with the numbers separated by a space. Notice that there must be no extra space at the end of each line.
Sample Input:
1 | 11 |
Sample Output:
1 | 1 13 12 21 33 34 38 27 22 32 |
题目分析
这道题大意很容易明白,也就是用已经存储好的Hash表来反推出其Hash表的插入顺序
由于是线性探测所以说每次有冲突情况都是向后移一位即j=(j+1)%N
,而由于是反推插入元素的冲突,所以说在线性探测目标位置之前都已经有元素插入
而如何存储插入的顺序呢
这里我们可以利用图的邻接矩阵来存储每一次的顺序,即入度和出度,而最后求出其插入顺序其实也就是拓扑排序,所以这道题最巧妙的一点就是在于其反推出的顺序即可以用拓扑排序还原其插入的顺序
代码实现
1 |
|