题目描述

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

I x，插入一个数 x；
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

图解

参考文献

y总

拉链法C++ 代码

#include <iostream>
#include <cstring>//memset的库
using namespace std;

/*
拉链法模一个数，这个数最好是个质数，这样冲突的概率就会少一点。由于大于10的第一个
质数是100003，所以N取这个数。
*/
const int N = 100003;
//h数组：哈希表存放数的空间   e数组模拟链表，存放的值   ne是链表的指针指向下一个元素
int h[N] , e[N] , ne[N] , idx;//idx表示当前用到了哪一个位置

//插入操作
void insert(int x){
    /*k哈希值。把−109≤x≤109映射到1≤N≤105 。
    C++中：取模运算，负数取模是负数，正数取模是正数。所以这里+N之后就一定
    是一个整数，然后再模N，变回正数的模。
    */
    int k = (x % N + N) % N ;
    //存入当前点
    e[idx] = x;
    //当前结点指向下一个元素的指针指向哈希值k
    ne[idx] = h[k];
    //哈希值k当前这一个结点已经用过了，所以要走到下一个结点，加加
    h[k] = idx++;
}

//查询操作
bool find(int x){
    int k = (x % N + N) % N;
    //找到k之后，然后在k这个链表中看看有没有这个数
    for(int i = h[k] ; i != -1 ; i = ne[i]){
        //找到x
        if(e[i] == x){
            return true;
        }
    }
    //没找到
    return false;
}

int main(){
    int n;
    scanf("%d" , &n);

    //初始化h数组，空指针用-1表示
    memset(h , -1 ,sizeof h);

    //开始进行两种操作，插入和询问
    while(n--){
        /*
        如果是读入一个字符串的，用scanf，因为他会把空格、制表符和回车给忽略掉。
        但是一般不要用scanf读入字符，否则有一些题会加额外的空格来卡
        */
        char op[2];
        int x;
        scanf("%s%d" , &op , &x);
        if(*op == 'I'){//插入操作
            insert(x);   
        }else{//查询操作
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

开放寻址法C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//开放寻址法，取的数要是原数据范围的2-3倍，切最好是一个质数
//null是定义一个数据范围之外的数，标记某个数在哈希表是否存在
const int N = 200003 , null = 0x3f3f3f3f;
//h哈希表
int h[N] ;

/*
find函数，如果x在哈希表中已经存在，那就返回这个位置；如果x在哈希表不存在，那
就返回x应该存储的位置
*/
int find(int x){
     /*k哈希值。把−109≤x≤109映射到1≤N≤105 。
    C++中：取模运算，负数取模是负数，正数取模是正数。所以这里+N之后就一定
    是一个整数，然后再模N，变回正数的模。
    */
    int k = (x % N + N) % N;

    //查询到当前位置有值在，并且不是x的话，那么x就要相应的往下一个位置走
    while(h[k] != null && h[k] != x){
        k++;
        //如果循环走到最后都没有发现一个空闲的位置，那就从哈希表的第一个值在找一下
        if(k == N ) k = 0;

    }
    //返回k
    return k;

}

int main(){
    int n ; 
    scanf("%d" , &n);
    //初始化哈希表，初始设为一个很大的值，表示这个位置是空的
    memset(h , 0x3f , sizeof h);

    while(n--){
        //op字符数组对应的每个操作
        char op[2];
        //x要插入或查询的值
        int x;
        scanf("%s%d" , &op , &x);

        //插入操作，找到x这个值的对应位置
        int k = find(x);
        if(*op == 'I'){
            //然后直接让这个位置赋值x就可以
            h[k] = x;
        }else{
            //查找操作，k值如果不是初始设置的标记值，那就说明哈希表有这个值
            if(h[k] != null) puts("Yes");
            else puts("No");
        }

    }
    return 0;
}