选网站建设公司有什么注意的,福田瑞沃自卸车官网,网站seo推广方案,给艺术家做网站的工作这道题主要在于思路#xff0c;感觉像个模拟题#xff0c;用到了线性探测的算法 机翻
1、条件准备
visit数组看这个位置有没有放进来数#xff0c;num存非负整数#xff0c;s存未到放入时机的数。 answer存答案。n为总共数量。
#include iostream
#include…这道题主要在于思路感觉像个模拟题用到了线性探测的算法 机翻
1、条件准备
visit数组看这个位置有没有放进来数num存非负整数s存未到放入时机的数。 answer存答案。n为总共数量。
#include iostream
#includeset
#includevector
#includealgorithm
#includeclimits
using namespace std;
#define endl \nint visit[1005];
vectorint num;
setint s;
vectorint answer;
int n;2、主函数
先输入存入Hash也就是放原始哈希表然后调用init函数再建立answer数组最后输出。
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;vectorint Hash(n);init(Hash,num);insertanswer(Hash);for(int i0;ianswer.size()-1;i)coutanswer[i] ;coutanswer[answer.size()-1];return 0;
}3、init函数
初始化Hash数组把非负整数放进num数组中然后排序因为我们要数尽可能小的优先输出所以要从小到大进行判断
void init(vectorintHash,vectorintnum)
{for(int i0;in;i){cinHash[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(vectorint Hash)
{for(int i0;inum.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(vectorint Hash,int elem)
{int idxelem%n;while(Hash[idx]!elem){if(visit[idx]0)return 0;idx(idx1)%n;}if(elemHash[idx]){visit[idx]1; return 1;}return 0;
}6、setinsert函数
先把数都放进数组里然后循环判断如果不能放就继续能放就放并删除该元素返回1. 都不能放返回0
bool setinsert(vectorint Hash,int up)
{vectorint t(s.begin(),s.end());for(int i0;it.size();i){int elemt[i];if(inserthash(Hash,elem)0||elemup)continue;s.erase(elem);answer.push_back(elem);return 1;}return 0;
}7、总结
感觉像个模拟题算法方面性不强偏思维题推导 完整代码如下
#include iostream
#includeset
#includevector
#includealgorithm
#includeclimits
using namespace std;
#define endl \nint visit[1005];
vectorint num;
setint s;
vectorint answer;
int n;bool inserthash(vectorint Hash,int elem)
{int idxelem%n;while(Hash[idx]!elem){if(visit[idx]0)return 0;idx(idx1)%n;}if(elemHash[idx]){visit[idx]1; return 1;}return 0;
}
bool setinsert(vectorint Hash,int up)
{vectorint t(s.begin(),s.end());for(int i0;it.size();i){int elemt[i];if(inserthash(Hash,elem)0||elemup)continue;s.erase(elem);answer.push_back(elem);return 1;}return 0;
}void init(vectorintHash,vectorintnum)
{for(int i0;in;i){cinHash[i];if(Hash[i]0)num.push_back(Hash[i]);}sort(num.begin(),num.end());
}
void insertanswer(vectorint Hash)
{for(int i0;inum.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);cinn;vectorint Hash(n);init(Hash,num);insertanswer(Hash);for(int i0;ianswer.size()-1;i)coutanswer[i] ;coutanswer[answer.size()-1];return 0;
}
