https://pintia.cn/problem-sets/994805342720868352/problems/994805389634158592
不得不說，讀了半天的假題，以為就是直接判斷可不可以插入就行了。
后來，發現是用只具有正增量的二次探測法來解決沖突。
不得不說，PAT的題還是很不錯的，考的是一些數據結構方面的一些內功，不是偏競賽的那種思維的。
考察的就是基本算法概念用算法來實現。
首先，先介紹一下二次探測法
關于二次探測法(處理沖突方法)：pos=(key + i*i )%MSize，其中i為 1*1 , -1*1 , 2*2 , -2*2 , ··· k*k , -k*k (k <= MSize-1)
題目說的是只具有正增量的二次探測法故pos=(key + i*i )%MSize，其中i為 1*1 , 2*2 , ··· k*k (k <= MSize-1)

#include<bits/stdc++.h> using namespace std; const int N=1e7+10; const int null=0x3f3f3f3f; int hush[N],n,m; int insert(int x) {for(int i=0;i<m;i++){int pos=(x+i*i)%m;if(hush[pos]==null)//找到位置了{hush[pos]=x;return pos;}}return -1; } bool check(int x) {if(x==1) return true;for(int i=2;i<=x/i;i++) if(x%i==0) return true;return false; } int main(void) {memset(hush,0x3f,sizeof hush);cin>>m>>n;while(check(m)) m++;//求最小的質數for(int i=1;i<=n;i++){int x; cin>>x;int ans=insert(x);if(ans==-1) cout<<"-";else cout<<ans;if(i!=n) cout<<" ";}return 0; }

總結

以上是生活随笔為你收集整理的1078 Hashing (25 分)【难度: 一般 / 知识点: 哈希表二次探测法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。