题目描述

维护一个集合，支持下面两种操作吗，共输入N个操作；
1. I x，插入一个数 x；
2. Q x，询问数 x 是否在集合中出现过，输出结果；

样例

5
I 1
I 2
I 3
Q 2
Q 5

Yes
No

算法1

散列表开放寻址法

散列表是将关键键值映射到哈希表中一个位置来进行访问的数据结构；这个映射的函数叫散列函数，存放记录的数组叫散列表；

开放寻址法是当发生冲突时的解决方法，当两个或以上键值映射到散列表的同一个位置时，如果发现该位置已经有元素，则看它前一位有没有元素，如果有，则再向前一位，直到存入数据；

散列表大小最好要选择大于数据量的最小质数，离2的幂远一点更好， 可以降低冲突概率；

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5+7, null = 0x3f3f3f3f;

int h[N];

int find(int x){                //散列函数加开放寻址；
    int t = (x%N+N) % N;
    while(h[t] != null && h[t] != x) if(++t == N) t = 0;
    return t;
}

int main()
{
    ios::sync_with_stdio(false);

    memset(h, 0x3f, sizeof h);
    int n, x;
    char op;
    cin>>n;
    while(n--){
        cin>>op>>x;
        if(op == 'I') h[find(x)] = x;
        else cout<< (h[find(x)] == x ? "Yes" : "No")<<endl;
    }
    return 0;
}

算法2

散列表拉链法

拉链法是另一种解决哈希冲突的办法，是将哈希到同一个位置的元素做成一个单链表挂在该位置；

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5+7;

int h[N], e[N], ne[N], idx;
//h[]为哈希数组，e[]存每个节点的具体值，ne[]用来寻找同一个位置上的节点；

void insert(int x){
    int t = (x%N+N)%N;
    e[++idx] = x;
    ne[idx] = h[t];
    h[t] = 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;
}

int main()
{
    ios::sync_with_stdio(false);

    int n, x;
    char op;
    memset(h, -1, sizeof h);
    cin>>n;
    while(n--){
        cin>>op>>x;
        if(op == 'I') insert(x);
        else cout<<(find(x) ? "Yes" : "No")<<endl;
    }
    return 0;
}