题目描述

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

I x，插入一个整数 x；
Q x，询问整数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。

样例

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200003;
//,去一个质数，用于较好的处理冲突，定义一个不在范围内的数，表示数组初始值
int h[N];
int n;
//闭散列方法(开放地址法）：
const int null=0x3f3f3f3f;
int find(int x)
{
    int t=(x%N+N)%N;
    while(h[t]!=null&&h[t]!=x)
         t=(t+1)%N;
    return t;
}
int main()
{
    memset(h,0x3f,sizeof h);
    cin >>n;
    while(n--)
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0]=='I')h[find(x)]=x;
        else 
        {
            if(h[find(x)]==null)puts("No");
            else puts("Yes");
        }
    }
    return 0;
}
//开散列
int n;
//开散列方法
//用数组模拟单链表
int h[N],e[N],ne[N],idx;
//开散列方法：

int e[N],ne[N],idx;
bool find(int x)
{
    int t=(x%N+N)%N;
    for(int i=h[t];i!=-1;i=ne[i])
    {
        if(e[i]==x)
        {
            return true;
        }

    }
    return false;
}
void add(int t,int x)
{
    e[idx]=x;
    ne[idx]=h[t];
    h[t]=idx;
    idx++;

}
void insert(int x)
{
    if(find(x))return ;
    int t=(x%N+N)%N;
    //防止有负数的余数
    add(t,x);
}

int main()
{
    memset(h,-1,sizeof h);
    cin >> n;
    while(n--)
    {
      char op[2];
      int x;
      scanf("%s%d",op,&x);
      if(op[0]=='I')insert(x);
      else 
      {
          if(find(x))puts("Yes");
          else puts("No");
      }
    }

    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla