AcWing 2951. 拉链法哈希
原题链接
中等
作者:
成为一个优秀的人
,
2022-02-22 14:10:27
,
所有人可见
,
阅读 272
#include<iostream>
#include<cstring>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
typedef long long ll;
const int N = 5e4 + 5, M = 50021; //M为比50000大的最小质数
int a[M];
int h[M], e[M], ne[M], idx;
void insert(int x){
int k = (x % M + M) % M;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++;
}
bool kfind(int x){
int k = (x % M + M) % M;
for(int i = h[k]; i != -1; i = ne[i]){
if(e[i] == x) return true;
}
return false;
}
int main(){
int t;
cin>>t;
while(t -- ){
int n;
cin>>n;
idx = 0;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++ ) cin>>a[i];
for(int i = 1; i <= n; i ++ ){
if(!kfind(a[i])){
insert(a[i]);
cout<<a[i]<<" ";
}
}
cout<<'\n';
}
// for(int i = 50000; ; i ++ ){
// bool flag = true;
// for(int j = 2; j <= i / j; j ++ ){
// if(i % j == 0){
// flag = false;
// break;
// }
// }
// if(flag){
// cout<<i;
// break;
// }
// }
return 0;
}