PAT-Hashing (25)

题目来源

Hashing (25)

题面点击链接自行查看

注意点

• 哈希探测用正向平方探测（二次探测），通常的平方探测是先加后减，这里只用正增量就不用减

思路简介

素数筛+二分查找确定表长
之后模拟哈希平方探测即可

当然直接一个一个找素数也是可以的，你问我为什么用素数筛，当然是因为帅
素数筛不难写，同时效率更高
个人觉得如果了解素数筛的话其实写代码的难度跟朴素找素数差不多
当然考试的时候会写朴素找就行了

遇到的问题

1. 哈希平方探测的增量上限是表长table.size()，超过表长的话，取模后相当于再次从 0 开始增加

代码

/** * https://www.nowcoder.com/pat/5/problem/4308 * 找素数 */#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+100;intk=0;//欧拉筛记录素数的个数vector<int>prime(N,0),vis(N,0);voidEuler_sieve(){for(inti=2;i<N;++i){if(!vis[i])prime[k++]=i;for(intj=0;j<k&&i*prime[j]<N;++j){vis[prime[j]*i]=1;//筛掉合数if(!(i%prime[j]))break;/* i是prime[j]的倍数时 说明后面的含有prime[j]的因子合数已经被筛选掉 不用重复筛选，退出 */}}}voidsolve(){Euler_sieve();intMsize,n;cin>>Msize>>n;intt=lower_bound(prime.begin(),prime.begin()+k,Msize)-prime.begin();Msize=prime[t];vector<int>hash(Msize,0);for(inti=0;i<n;++i){intk,j;cin>>k;for(j=0;j<Msize;++j){intpos=(k+j*j)%Msize;if(hash[pos])continue;hash[pos]=1;cout<<pos;break;}if(j==Msize)cout<<'-';if(i!=n-1)cout<<' ';}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());intT=1;//cin>>T;while(T--){solve();}return0;}