题解1:拉链法
复杂度分析:
- 时间复杂度:query()为O(1),insert(1)
- 空间复杂度O(n)
import java.util.*;
import java.io.*;
class Main {
static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static final int N = (int)(1e5 + 3);
static int n;
//开一个槽:邻接表写法(单列表)
static int[] e = new int[N], ne = new int[N], h = new int[N];
static int idx;
public static void insert(int num) {
int k = (num % N + N) % N;
//创建一个节点
e[idx] = num;
ne[idx] = h[k];
//插入到对应的插槽中
h[k] = idx++;
}
public static boolean query(int num) {
int k = (num % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i]) {
if (e[i] == num) return true;
}
return false;
}
public static void main(String[] args) throws Exception{
n = Integer.parseInt(cin.readLine());
//初始化槽
Arrays.fill(h, -1);
while (n-- != 0) {
String[] ss = cin.readLine().split(" ");
String type = ss[0];
int num = Integer.parseInt(ss[1]);
if ("I".equals(type)) {
insert(num);
}else {
System.out.println(query(num) ? "Yes" : "No");
}
}
}
}
题解2:开放寻址法
复杂度分析:时间复杂度O(n);空间复杂度O(1)
import java.util.*;
import java.io.*;
class Main {
static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
//开放寻址法:N一般开数据范围的2到3倍。大于数据范围的第一个质数
//规定空指针范围为最大
static final int N = (int)(2e5 + 3), Nll = Integer.MAX_VALUE;
static int[] h = new int[N];
//寻找到一个开放的空间位置
public static int find(int x) {
int k = (x % N + N) % N;
//寻找到一个为空的位置 或者说找到目标x的位置结束
while (h[k] != Nll && h[k] != x) {
//地址进行+1
k++;
if (k == N) k = 0;
}
return k;
}
public static void main(String[] args) throws Exception{
int n = Integer.parseInt(cin.readLine());
//初始化槽
Arrays.fill(h, Nll);
while (n-- != 0) {
String[] ss = cin.readLine().split(" ");
String type = ss[0];
int num = Integer.parseInt(ss[1]);
if ("I".equals(type)) {
//找到对应位置为NILL的,进行插入
h[find(num)] = num;
}else {
//若是对应的空间位置为NLL表示没有找到
System.out.println(h[find(num)] != Nll? "Yes" : "No");
}
}
}
}