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.
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.
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.
11
33 1 13 12 34 38 27 22 32 -1 21
1 13 12 21 33 34 38 27 22 32
/*知道散列数组大小，和散列数组值反求输入数组*/ #include<cstdio> #include<cstdlib> #include<set> using namespace std; const int maxn = 1010; int G[maxn][maxn]; void BuildGraph(int hash[], int n); void TopSort(int hash[], int hashMap[], int n, int num); int main() { int n; int num = 0; //纪录hash表中元素个数 int hash[maxn], hashMap[maxn]; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &hash[i]); hashMap[hash[i]] = i; if (hash[i] >= 0) { num++; } } BuildGraph(hash, n); TopSort(hash, hashMap, n, num); return 0; } void BuildGraph(int hash[], int n) { for (int i = 0; i < n; i++) { if (hash[i] >= 0) { int tmp = hash[i] % n; //对应采用线性检查法解决碰撞的元素 if (hash[tmp] != hash[i]) { for (int j = tmp; j != i; j = (j+1) % n) //建立有向拓扑图来 { G[j][i] = 1; //凡是在这个元素之前的位置，都要依赖他们先输入 } } } } } void TopSort(int hash[], int hashMap[], int n, int num) { int cnt = 0; int Indegree[maxn] = {0}; set<int> s; for (int v = 0; v < n; v++) { for(int w = 0; w < n; w++) { if (G[v][w] != 0) { Indegree[w]++; } } } for (int i = 0; i < n; i++) { if (Indegree[i] == 0 && hash[i] > 0) { s.insert(hash[i]); } } while (!s.empty()) { int now = hashMap[*s.begin()]; s.erase(s.begin()); cnt++; printf("%d", hash[now]); if (cnt != num) { printf(" "); } for (int v = 0; v < n; v++) { if (G[now][v] != 0) { if (--Indegree[v] == 0) { s.insert(hash[v]); } } } } }
11-散列4 Hashing - Hard Version (30 分)
原文：https://www.cnblogs.com/wanghao-boke/p/11964366.html