题目描述
维护一个集合,支持如下几种操作:
I x
,插入一个数 $x$;Q x
,询问数 $x$ 是否在集合中出现过;
现在要进行 $N$ 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 $N$,表示操作数量。
接下来 $N$ 行,每行包含一个操作指令,操作指令为 I x
,Q x
中的一种。
输出格式
对于每个询问指令 Q x
,输出一个询问结果,如果 $x$ 在集合中出现过,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
$1≤N≤10^5$
$−10^9≤x≤10^9$
样例
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
算法1
拉链法
时间复杂度
$O(1)$
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
// 拉链法实现
// 取模的数一定要是质数
// 由于 1≤N≤105 , 先求大于10^5 的最小质数
// for (int i=100000;;i++){
// bool flag = true;
// for (int j=2; j*j <= i; j++)
// if (i%j ==0)
// {
// flag = false;
// break;
// }
// if (flag)
// {
// cout<<i<<endl;
// break;
// }
// }
// 求出大于 100000 的最小质数是100003
const int N = 100003; // 先求出大于10^5的第一个质数
// h[N] 为存储链头的集合
// 拉的链就是链表, e[N] ne[N] idx的含义和链表中的含义相同
// e[N] 存储每个节点的值
// ne[N] 存储该节点指向的下一个节点
// idx 当前用到的哪个个位置
int h[N], e[N], ne[N], idx;
// 插入函数
void insert(int x)
{
int k = (x%N + N) % N; // 加N模N 用来处理x是负数的情况
// 单链表插入
e[idx] = x, ne[idx] = h[k], h[k] =idx, idx++;
}
// 查询函数
bool find(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()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof h); // 将h[N]各个链头初始化为-1, 表示链表为空(集合为空
while(n--)
{
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;
}
算法2
开放寻址法
时间复杂度
$O(1)$
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
// 拉链法实现
// 取模的数一定要是质数
// 由于 1≤N≤105 , 先求大于10^5 的最小质数
// for (int i=100000;;i++){
// bool flag = true;
// for (int j=2; j*j <= i; j++)
// if (i%j ==0)
// {
// flag = false;
// break;
// }
// if (flag)
// {
// cout<<i<<endl;
// break;
// }
// }
// 求出大于 100000 的最小质数是100003
const int N = 100003; // 先求出大于10^5的第一个质数
// h[N] 为存储链头的集合
// 拉的链就是链表, e[N] ne[N] idx的含义和链表中的含义相同
// e[N] 存储每个节点的值
// ne[N] 存储该节点指向的下一个节点
// idx 当前用到的哪个个位置
int h[N], e[N], ne[N], idx;
// 插入函数
void insert(int x)
{
int k = (x % N + N) % N; // 加N模N 用来处理x是负数的情况
// 单链表插入
e[idx] = x, ne[idx] = h[k], h[k] =idx, idx++;
}
// 查询函数
bool find(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()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof h); // 将h[N]各个链头初始化为-1, 表示链表为空(集合为空
while(n--)
{
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;
}