宣传一下 算法基础课整理
题目描述
维护一个集合,支持如下几种操作:
1.I x
,插入一个数 $x$;
2.Q x
,询问数 $x$ 是否在集合中出现过;
现在要进行 $N$ 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 $N$,表示操作数量。
接下来 $N$ 行,每行包含一个操作指令,操作指令为 I x
,Q x
中的一种。
输出格式
对于每个询问指令 Q x
,输出一个询问结果,如果 $x$ 在集合中出现过,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
$1 \le N \le 10^5$
$-10^9 \le x \le 10^9$
样例
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
简要题意就是让你维护一个集合,判断一个数有没有出现过
但$x$范围很大,所以要用哈希表(所以map, Treap它不香吗?)
哈希表重点在于设计哈希函数,哈希函数的目的是把一个数映射成一个不差过n的数,类似离散化,但要尽量不重复,越不重复,哈希表越快
而哈希函数会重复,所以用两种解决方法:
哈希一共有两种写法,一种是拉链法,一种是开放寻址法
拉链法:用邻接表来串起哈希函数相同的值(要有邻接表基础)
开放寻址法:若该位置已有数了,则存在下标$+1$的位置
我个人喜欢拉链法,开放寻址法我不常用,喜欢哪种看大家自己选择
算法1
(拉链法) $O(玄学)$
时间复杂度 哈希表期望复杂度O(1),但因为哈希函数冲突而变得很玄学
参考文献 我个人认为 这篇文章 写得挺好的
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200003;
int n, h[N], e[N], ne[N], idx;
int H(int x) {
return (x % N + N) % N;
}
int find(int x) {
int k = H(x);
for (int i = h[k]; ~i; i = ne[i]) //查询
if (e[i] == x)
return 1;
return -1;
}
void insert(int x) {
int k = H(x);
e[idx] = x, ne[idx] = h[k], h[k] = idx ++ ; //基本邻接表插入
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(h, -1, sizeof h);
cin >> n;
while (n -- ) {
char op;
int x, k;
cin >> op >> x;
if (op == 'Q') {
k = find(x);
if (k == -1) puts("No");
else puts("Yes");
}
else insert(x);
}
return 0;
}
算法2
(开放寻址法) $O(玄学)$
他一个特别之处是他如果没找到,返回值是下一个插入位置
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int n, h[N];
int find(int x) {
int k = (x % N + N) % N;
while (h[k] != null && h[k] != x) {
k ++ ;
if (k == N) k = 0;
}
return k;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(h, null, sizeof h);
cin >> n;
while (n -- ) {
char op;
int x, k;
cin >> op >> x;
k = find(x);
if (op == 'I') {
h[k] = x;
}
if (op == 'Q') {
if (h[k] != null) puts("Yes");
else puts("No");
}
}
return 0;
}
算法3
(map) STL大法好!
c++代码
//自己应该会写吧,我懒得写了