Acwing---840. 模拟散列表

2024-02-12 23:28

文章标签 模拟列表 acwing 840

本文主要是介绍Acwing---840. 模拟散列表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模拟散列表

1.题目
2.基本思想
3.代码实现

1.题目

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

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

2.基本思想

开放寻址法
1.将x映射成小数组下标k，如果不同x所得k相同，则存储到k+1位置，以此类推
需要维护的变量：N:操作所需空间数量的两倍 , h[N]：寻址数组

寻找所需10^5空间 2倍大的第一个质数

import java.io.IOException;public class _840模拟散列表1 {public static void main(String[] args) throws IOException {for (int i = 200000; ; i++) {boolean flag = true;for (int j = 2; j * j <= i; j++) {if (i % j == 0) {flag = false;break;}}if (flag) {System.out.println(i);break;}}}
}

HashMap

3.代码实现

开放寻址法

import java.io.*;
import java.util.*;public class Main {static int N = 200003;static Integer[] h = new Integer[N];  //因为要用null标识节点空，所以类型为Integervoid init_h() {   //先将所有位置设为null，标识为空Arrays.fill(h, null);}private static int find(int x) {//函数返回：存在x 返回存储下标 ； x不在数组，返回应插入位置int k = (x % N + N) % N;//这里 由于x可能很小因而需要先 mod 再加Nwhile (h[k] != null && h[k] != x) {k++;if (k == N) k = 0;}return k;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());while (n-- > 0) {String[] s = br.readLine().split(" ");String opt = s[0];int x = Integer.parseInt(s[1]);int k = find(x);if (opt.equals("I")) h[k] = x;else if (opt.equals("Q")) {if (h[k] != null) System.out.println("Yes");else System.out.println("No");}}}
}

Map

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;public class _840模拟散列表 {static int N = 100010;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));Map map = new HashMap<Integer, Integer>();int n = Integer.parseInt(br.readLine());while (n-- > 0) {String[] s = br.readLine().split(" ");String opt = s[0];if (opt.equals("I")) {int x = Integer.parseInt(s[1]);map.put(x, x);} else if (opt.equals("Q")) {int x = Integer.parseInt(s[1]);if (map.get(x) != null) System.out.println("Yes");else System.out.println("No");}}}
}