题目描述

维护一个集合，支持如下几种操作：

1.“I x”，插入一个数x；
2.“Q x”，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数N，表示操作数量。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。

输出格式
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109

样例

输入:
5
I 1
I 2
I 3
Q 2
Q 5
输出:
Yes
No

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

开放寻址法
#include<bits/stdc++.h>
using namespace std;
const int N=200003,null=0x3f3f3f3f;
int h[N];
int find(int x)          // 返回h[t]为空或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;
    cin>>n;
    memset(h,0x3f,sizeof h);
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;
        if(op[0]=='I') h[find(x)]=x;
        else {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

拉链法
#include<bits/stdc++.h>
using namespace std;
const int N=100003;
int e[N],ne[N],h[N],idx;
void insert(int x)    //插入，详细可学习单链表
{
    int k=(x%N+N)%N;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
int query(int x)   //查找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;
    cin>>n;
    memset(h,-1,sizeof h);
    while(n--)
    {
        char op[3];
        int x;
        cin>>op;
        if(op[0]=='I') cin>>x,insert(x);
        else {
            cin>>x;
            (query(x))?puts("Yes"):puts("No");   // 等于if(query(x)) puts("Yes"); else puts("No");
        }
    }
}