题目描述

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

    1. I x，插入一个数 x；
    2. Q x，询问数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

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

数据范围

1 ≤ N ≤ 1e5
−1e9 ≤ x ≤ 1e9

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

算法1 (开放寻址法解决哈希地址冲突)

C++ 代码

#include <iostream>
#include <cstring>  //使用memset()

using namespace std;

const int N = 2e5 + 3;  //数组长度一般取操作数的2~3倍的质数 (2e5+3是距离2e5最近的质数)
const int INF = 0x3f3f3f3f;  //设置一个标记数(超出数据范围即可)

int h[N];

//返回x的下标, 若x不存在, 则返回x应该插入的下标
int find(int x) {
    int k = (x % N + N) % N;

    while(h[k] != INF && h[k] != x) {
        k++;
        if(k == N) k = 0;   //遍历到数组结尾则重新从头遍历
    } 

    return k;
}

int main() {
    memset(h, 0x3f, sizeof h);    //memset按字节赋值, 4个字节都赋值为0x3f

    int n; cin >> n;
    while(n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        int k = find(x);
        if(*op == 'I') h[k] = x;
        else {
            if(h[k] != INF) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

算法2 (拉链法解决哈希地址冲突)

C++ 代码

#include <iostream>
#include <cstring>  //使用memset()

using namespace std;

const int N = 1e5 + 3;  //距离1e5最近的质数

int h[N], e[N], ne[N], idx;

void insert(int x) {
    int k = (x % N + N) % N;    //保证k大于等于0
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool query(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() {
    memset(h, -1, sizeof h);    //指针全部初始化为-1
    int n; cin >> n;
    while(n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op == 'I') insert(x);
        else {
            if(query(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}