Hashing - Hard Version

Given a hash table of size N, we can define a hash function . 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

11

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

Sample Output:

1 13 12 21 33 34 38 27 22 32

分析

参考Messier

可以使用拓扑排序来解这道题。基本思路如下：将输入保存在散列表后，遍历每个元素，如果元素刚好在它对应余数的位置上，则入度为0，可直接输出；否则，从余数位置出发，用线性探测法到达该位置，对于经过的所有的非空元素位置，生成一条到该元素位置的边，并将该位置入度加1；拓扑排序时，可以采用优先队列，优先输出数值较小的元素

代码如下

#include<iostream>

#include<queue>

#include<algorithm>

using namespace std;

vector<int> G[1000]; // 连接表

int N;

int indegree[1000]={0}; // 入度

int a[1000];

struct mycompare{ // 为优先队列自定义操作

	bool operator()(int m,int n){

		return a[m]>a[n];

	}

};

void toposort(){ // 拓扑排序

	int tag=0;

	priority_queue<int,vector<int>,mycompare> q;

	for(int i=0;i<N;i++)

	if(indegree[i]==0&&a[i]>=0)

	q.push(i);

	while(!q.empty()){

		int t=q.top();

		if(tag++==0) cout<<a[t];

		else cout<<" "<<a[t];

		q.pop();

		for(int i=0;i<G[t].size();i++){

			int v=G[t][i];

			indegree[v]--;

			if(indegree[v]==0)

			q.push(v);

		}

	}

}

int main(){

	cin>>N;

	for(int i=0;i<N;i++)

	cin>>a[i];

    for(int i=0;i<N;i++){ // 建图

    	if(a[i]%N==i||a[i]<0)

		continue;

    	else

		{

		    int t=a[i]%N;

    		while(t!=i){

    			G[t].push_back(i);

    			indegree[i]++;

    			t=(t+1)%N;

			}

		}

	}

	toposort();

	return 0;

}

巴特西

Hashing - Hard Version

Hashing - Hard Version

分析

代码如下

最新文章

热门文章