AcWing 1638. 哈希 - 平均查找时间
原题链接
简单
作者:
eveer
,
2021-08-30 14:26:54
,
所有人可见
,
阅读 229
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N];//h[i]表示当前位置是否有元素插入
int cnt[N];//cnt[i]表示数值i的查询次数,做一个记忆的存储,避免重复多次查询相同元素
int main()
{
int msize,n,m;//msize表示用户设置的hash表大小,n表示节点的数量,m表示查询的数量
scanf("%d%d%d",&msize,&n,&m);
memset(cnt,-1,sizeof cnt);//记录数值i的访问次数,初始化为-1,是为了后面可以进行if语句判断
for(int i=msize;;i++)
{
if(i==1)//表示用户输入的是一个1,1不是质数,直接特判
{
msize=2;
break;
}
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=0;i<n;i++)//循环n次读入所需的数据
{
int x;
scanf("%d",&x);
bool is_in=false;//表示这个元素我是否可以插入
for(int j=0;j<=msize-1;j++)//平方探测法
{
if(h[(x+j*j)%msize]==false)//表示这个位置,当前还没有元素插入过
{
h[(x+j*j)%msize]=true;
cnt[x]=j+1;//记录当下的x是查询了几次获得的
is_in=true;//表示这个元素我可以找到一个位置插入
break;//找到了可以放的位置就退出
}
}
if(is_in==false)//表示这个元素我找不到位置插入
{
printf("%d cannot be inserted.\n",x);
cnt[x]=msize+1;//需要注意的是如果msize次内都没有找到,那么查找次数是msize+1
}
}
float sum=0;//记录总的查询次数
for(int i=0;i<m;i++)//查询元素的判断
{
int x;
scanf("%d",&x);
if(cnt[x]==-1)//表示这个元素,我之前都没有查找过
{
bool is_in=false;//表示这个元素我是否可以插入
for(int j=0;j<=msize-1;j++)//平方探测法
{
if(h[(x+j*j)%msize]==false)//表示找到了这个位置,当前还没有元素插入过
{
cnt[x]=j+1;//记录当下的x是查询了几次获得的
sum+=cnt[x];
is_in=true;//表示这个元素我可以找到一个位置插入
break;//找到了可以放的位置就退出
}
}
if(is_in==false)//表示这个元素我找不到位置
{
cnt[x]=msize+1;
sum+=cnt[x];
}
}
else//如果这个元素之前已经存入过了,那么我直接加上这个次数就可以了
sum+=cnt[x];
}
printf("%.1f",sum/m);
return 0;
}