AcWing 1564. 哈希
原题链接
简单
作者:
eveer
,
2021-08-28 00:41:42
,
所有人可见
,
阅读 306
/*
二次方探查法:(key + step * step) % MSize
其中,step步长从1加到MSize-1,如果遍历完之后都不能找到位置放元素,
则说明这个数字放不进去,否则输出这个位置即可
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2010;//数组范围先稍微开的大一些
int h[N];
bool st[N];//记录每一个位置上是否已经存储有元素
int main()
{
int size,n;//size表示用户输入的hash表大小,n表示需要插入的数据数量
scanf("%d%d",&size,&n);
int msize;
if(size==1)size=size+1;//在质数中,对于1的情况要格外地注意,需要进行特判
for(int i=size;;i++)
{
bool flag=true;
for(int j=2;j<=i/j;j++)
{
if(i%j==0)//能够整除,说明i不是质数
{
flag=false;
break;
}
}
if(flag==true)//说明我们已经找到了这个质数
{
msize=i;
break;
}
}
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
bool flag=false;//判断x元素是否可以放入hash中
int key;
for(int i=0;i<msize-1;i++)
{
key=(x+i*i)%msize;
if(st[key]==false)
{
st[key]=true;
flag=true;
break;
}
}
if(i==1)//保证格式的输入正确
{
if(flag==true)printf("%d",key);
else printf("-");
}
else
{
if(flag==true)printf(" %d",key);
else printf(" -");
}
}
return 0;
}