pat09-散列3. Hashing - Hard Version (30)
09-散列3. Hashing - Hard Version (30)
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:
11
33 1 13 12 34 38 27 22 32 -1 21
Sample Output:
1 13 12 21 33 34 38 27 22 32
主要思路:
哈希表规模为n。对于输入的位置编号为i的元素a,如果:
1.i==a%n。说明a放i位置不是由于冲突,将a放入优先队列。
2.i>a%n。如果编号为a%n到n-1的元素之前已经填入哈希表(h1[j].exist=true),则第i个元素可以进入优先队列。否则,如果编号为a%n到n-1的元素在位置编号为i的元素填入之后填入哈希表,意味着位置编号为i的元素插入哈希表时,发生冲突向后转移不可能到达位置i,而应该在i位置之前填入,矛盾。
3.i<a%n。与2同理。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node{
bool exist;
node(){
exist=false;
}
};
node h1[];
priority_queue< pair<int,int>,vector<pair<int ,int> >,greater<pair<int,int> > > pq;//记录值和放的位置,按pair的第一个元素升序排列
pair<int,bool> input[];//标记元素有没有进入队列
queue<int> q;
int main(){
//freopen("D:\\INPUT.txt","r",stdin);
int n,num,i,count=;
scanf("%d",&n);
for(i=;i<n;i++){
scanf("%d",&num);
input[i]=make_pair(num,false);
if(num>=){//记录不等于负数的元素个数
count++;
}
}
int j,k,post;
for(i=;i<count;i++){//复杂度n^2:扫数列count次,每次将当前满足条件的最小元素进入队列q
for(j=;j<n;j++){//遍历数列的每个元素
if(!input[j].second&&input[j].first>=){//寻找没有进入队列并且不等于-1的元素
post=input[j].first%n;//元素本来应该在哈希表中的位置
if(post==j){//本来要放的位置和现在在哈希表中的位置相同
pq.push(make_pair(input[j].first,j));
//h1[post].exist=true;//标记
input[j].second=true;
continue;
}
if(post<j){//本来要放的位置在现在的位置前面
for(k=post;k<j;k++){
if(!h1[k].exist){//前面没有元素填充
break;
}
}
if(k==j){//可以进队pq
pq.push(make_pair(input[j].first,j));
//h1[j].exist=true;
input[j].second=true;
}
}
else{//post>j
for(k=post;k<n;k++){//先由post开始向后遍历
if(!h1[k].exist){
break;
}
}
if(k==n){//满足条件后,由0开始向j遍历
for(k=;k<j;k++){
if(!h1[k].exist){
break;
}
}
if(k==j){
pq.push(make_pair(input[j].first,j));
//h1[j].exist=true;
input[j].second=true;
}
}
}
}
}
pair<int,int> top=pq.top();
pq.pop();
q.push(top.first);//找到本次满足条件:在队列pq且最小的元素,进入输出队列q
h1[top.second].exist=true;//意味着top.second位置已经放了元素
}
printf("%d",q.front());//对输出队列q进行输出
q.pop();
while(!q.empty()){
printf(" %d",q.front());
q.pop();
}
return ;
}
最新文章
- AHCI: Failed to attach drive to Port1 (VERR_GENERAL_FAILURE).
- Ubuntu 14.04.1 建立 Android M, Android N 開發環境 與 問題
- 第一个Leap Motion测试页面 (webgl/three/leapjs/leap)
- myeclipse中如何导入mysql-connector-java-5.1.8-bin.jar【环境配置和工具使用】
- PYTHON学习之路_PYTHON基础(3)
- Mac OS X Tips
- 给文件加ip访问限制
- java类转化为json对象
- javaWEB总结(4):ServletContext对象方法
- sql server 2008 数据库管理系统使用SQL语句创建登录用户详细步骤
- 超有料丨小白如何成功逆袭为年薪30万的Web安全工程师
- 2019年10个最受欢迎的JavaScript动画库!
- VUE(相关简介及初始)
- Android内存优化(四)LeakCanary使用详解
- vs2017 代码格式化 文档排版 编辑 设置文档的格式
- gulp项目和webpack项目在浏览器中查看的方式
- Command `bundle` unrecognized. Make sure that you have run `npm install` and that you are inside a react-native project.
- 讲解Linux数据库安装
- Web项目替换jar包中的文件的方法
- curl 用法总结
热门文章
- SharePoint 2013报错之“指定的文件不是有效的电子表格或者没有包含要导入的数据”
- android studio中使用recyclerview制作个显示考勤打卡的日历来
- owinAuthorize
- 怎样检查fragmentation
- 解决低版本Xcode不支持高版本iOS真机调试的问题
- 【转】如何不让DataGridView自动生成列
- 深度学习之 TensorFlow(三):TensorFlow 源代码解析
- JS内置对象的原型不能重定义?只能动态添加属性或方法?
- maven设置------settings.xml文件学习
- loj #2538. 「PKUWC2018」Slay the Spire