题目描述

分析：如果暴力来做，由于数的范围太大了，需要构造2 * 10^6范围的数组，因此要使用哈希函数。
同时：使用哈希函数肯定会发生冲突。
因为数组范围小，而数据多，因此可以使用两种方法：
拉链和开放寻址法.

开放寻址法：
相当于派一个人给x找坑位。
设置数组是最大数的两倍。这样保证坑位不会被占满。一定能找到坑。
find功能：
1.坑位判断：根据给定的值找对应的坑位的起始点。c取模是精准取模，负数取模的结果也是负数 因此取模方法K = ((x %N ) + N )% N
2.坑位就相当于数组位置。我从某一个位置开始找坑位，如果有人，并且坑位上的人不是x（h[k] != null && h[k] != x）
没关系，往下找。k;
3.当我走到厕所尽头，再从头找。If(k == n)k = 0;
找到坑,就返回我的位置。
return k;
插入功能：
前面提示找坑了find(x) != null, 那么h[find(x)] = x;把门关上，换成有人（更改状态）。
查询功能：
if(h[find(x)]!=null)如果这个人所在的坑位没有关上门，说明并没有占用。

样例

5
I 1
I 2
I 3
Q 2
Q 5

算法1

(哈希开放寻址) $O(1)$

时间复杂度

参考文献

基础课代码

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
/*0x3f3f3f3f > 10^9 表示当前坑位没有人*/
const int null = 0x3f3f3f3f;
const int N = 200010;
int h[N], n;

int find(int x)
{
      /*k 初始值不能设置成0，否则当数据范围增大了之后模N为0的数都没法存放*/

    int k = ((x % N) + N ) % N;
    while(h[k] != null && h[k] != x)
    {
        k++;
        if(k == N) k = 0;
    }
    return k;
}

int main()
{
    int n; cin >>n;
    memset(h, 0x3f ,sizeof(h));
    while(n--)
    {
        char op[2];int x;
        scanf("%s%d", op, &x);
        if(*op == 'I')
        {
            h[find(x)] = x;
        }
        else
        {
            if(h[find(x)] == null)puts("No");
            else puts("Yes");
        }
        //cout << h[find(5)];
    }
    return 0;
}