方法一：直接unordered_map

C++ 代码

#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<int,int> map;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char op;
        int x;
        cin>>op>>x;
        if(op=='I') map[x]++;
        else{
            if(map[x]) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

方法二：拉链法，数组模拟，要快不少

C++ 代码

//拉链法
#include<iostream>
#include<cstring>
using namespace std;
const int N=100003;
int h[N],e[N],ne[N],idx;
void insert(int x){
    int k=(x%N+N)%N;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
int find(int x){
    int k=(x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i]){
        if(e[i]==x) return true;
    }
    return false;
}
int main(){
    int n;
    scanf("%d",&n);
    //for(int i=0;i<N;i++) h[i]=-1;
    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示
    while(n--){
        char op;
        int x;
        cin>>op>>x;
        if(op=='I') insert(x);
        else{
            if(find(x)==true) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

方法三：开放寻址法

C++ 代码

//开放寻址法
#include<iostream>
#include<cstring>
using namespace std;
const int N=200003;
const int null=0x3f3f3f3f;
int h[N];
int find(int x){//返回存储的位置
    int t=(x%N+N)%N;
    while(h[t]!=null&&h[t]!=x){
        t++;
        if(t==N) t=0;
    }
    return t;
}
int main(){
    int n;
    scanf("%d",&n);
    memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3f
    while(n--){
        char op;
        int x;
        cin>>op>>x;
        if(op=='I') h[find(x)]=x;
        else{
            if(h[find(x)]==x) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}