浙大数据结构：11-散列4 Hashing - Hard Version

这道题主要在于思路，感觉像个模拟题，用到了线性探测的算法
机翻

1、条件准备

visit数组看这个位置有没有放进来数，num存非负整数，s存未到放入时机的数。
answer存答案。n为总共数量。

#include <iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
#define endl '\n'int visit[1005];
vector<int> num;
set<int> s;
vector<int> answer;
int n;

2、主函数

先输入存入Hash，也就是放原始哈希表，然后调用init函数，再建立answer数组，最后输出。

int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;vector<int> Hash(n);init(Hash,num);insertanswer(Hash);for(int i=0;i<answer.size()-1;i++)cout<<answer[i]<<' ';cout<<answer[answer.size()-1];return 0;
}

3、init函数

初始化Hash数组，把非负整数放进num数组中，然后排序，因为我们要数尽可能小的优先输出，所以要从小到大进行判断

void init(vector<int>&Hash,vector<int>&num)
{for(int i=0;i<n;i++){cin>>Hash[i];if(Hash[i]>=0)num.push_back(Hash[i]);}sort(num.begin(),num.end());
}

4、initanswer函数

遍历num数组，看能不能直接放入哈希表，即调用inserthash函数，如果不能就把数放进set中备用。
当我们遍历到后面某个数时，看看set中的数能不能插入哈希表，因为输出是多种可能数小的先输出，所以遍历set数组直到里面的数都不能放入哈希表，因为set里面的数比当前数大，再来判断当前数能否放入

void insertanswer(vector<int>& Hash)
{for(int i=0;i<num.size();i++){while(setinsert(Hash,num[i]));if(inserthash(Hash,num[i]))answer.push_back(num[i]);elses.insert(num[i]);}while(s.size())setinsert(Hash,INT_MAX);}

5、inserthash函数

先算出应该放入的下标，若这个下标对应的数不为当前数，则下标加1再取模。如果该位置的数还没放进来，说明当前数此时放早了，还不能放进来，返回0.
如果当前数与哈希表当前位置一样，则return 1，否则0.

bool inserthash(vector<int> &Hash,int elem)
{int idx=elem%n;while(Hash[idx]!=elem){if(visit[idx]==0)return 0;idx=(idx+1)%n;}if(elem==Hash[idx]){visit[idx]=1; return 1;}return 0;
}

6、setinsert函数

先把数都放进数组里，然后循环判断，如果不能放就继续，能放就放，并删除该元素，返回1.
都不能放返回0

bool setinsert(vector<int>& Hash,int up)
{vector<int> t(s.begin(),s.end());for(int i=0;i<t.size();i++){int elem=t[i];if(inserthash(Hash,elem)==0||elem>up)continue;s.erase(elem);answer.push_back(elem);return 1;}return 0;
}

7、总结

感觉像个模拟题，算法方面性不强，偏思维题＋推导
完整代码如下

#include <iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
#define endl '\n'int visit[1005];
vector<int> num;
set<int> s;
vector<int> answer;
int n;bool inserthash(vector<int> &Hash,int elem)
{int idx=elem%n;while(Hash[idx]!=elem){if(visit[idx]==0)return 0;idx=(idx+1)%n;}if(elem==Hash[idx]){visit[idx]=1; return 1;}return 0;
}
bool setinsert(vector<int>& Hash,int up)
{vector<int> t(s.begin(),s.end());for(int i=0;i<t.size();i++){int elem=t[i];if(inserthash(Hash,elem)==0||elem>up)continue;s.erase(elem);answer.push_back(elem);return 1;}return 0;
}void init(vector<int>&Hash,vector<int>&num)
{for(int i=0;i<n;i++){cin>>Hash[i];if(Hash[i]>=0)num.push_back(Hash[i]);}sort(num.begin(),num.end());
}
void insertanswer(vector<int>& Hash)
{for(int i=0;i<num.size();i++){while(setinsert(Hash,num[i]));if(inserthash(Hash,num[i]))answer.push_back(num[i]);elses.insert(num[i]);}while(s.size())setinsert(Hash,INT_MAX);}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;vector<int> Hash(n);init(Hash,num);insertanswer(Hash);for(int i=0;i<answer.size()-1;i++)cout<<answer[i]<<' ';cout<<answer[answer.size()-1];return 0;
}