浙大数据结构: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]);
else
s.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]);
else
s.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;
}
原文地址:https://blog.csdn.net/qq_74924951/article/details/142987776
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!