840. 模拟哈希表（模板）-白红宇

840. 模拟哈希表（模板）

阅读量：3967 次

发布时间：2019-05-24

本文共 2802 字，大约阅读时间需要 9 分钟。

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

“I x”，插入一个数x；

“Q x”，询问数x是否在集合中出现过；

现在要进行N次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数N，表示操作数量。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。

输出格式

对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围

输入样例：

5I 1I 2I 3Q 2Q 5

输出样例：

YesNo

两种存储方法

1.拉链法

一个数x，k=x%N，

N一般取大于操作数的第一个

质数

代码：

import java.util.Arrays;import java.util.Scanner;public class Main{        static final int N=100003;        static int e[]=new int[N];        static int ne[]=new int[N];        static int h[]=new int[N];        static int idx;        static void insert(int x){
   //其实就是单链表的头插法                int k=(x%N+N)%N;//x可能为负数，使它>=0                e[idx]=x;                ne[idx]=h[k];                h[k]=idx;                idx++;        }        static boolean 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;        }        public static void main(String[] args) {                Scanner scan=new Scanner(System.in);                int n=scan.nextInt();                Arrays.fill(h,-1);                while(n-->0){                        String op=scan.next();                        int x=scan.nextInt();                        if(op.equals("I")){                                insert(x);                        }                        else{                                if(find(x)) System.out.println("Yes");                                else System.out.println("No");                        }                }        }}

2.开放寻址法

基本思路：k=x%N ，如果这个位置没有数就放在这个位置，否则依次寻找下一个位置

代码：

import java.util.Arrays;import java.util.Scanner;public class Main{        static final int N=200003;//一般取数据范围N的2倍 的 大于它的第一个质数        static int INF=(int)1e9+5;        static int h[]=new int[N];                static int find(int x){                int k=(x%N+N)%N;                while(h[k]!=INF && h[k]!=x){
   //这个位置有数并且不等于x                     k++;//寻找下一个位置                     if(k==N) k=0;//找到最后一个位置，从头开始寻找                }                return k;        }                public static void main(String[] args) {                Scanner scan=new Scanner(System.in);                Arrays.fill(h,INF);//初始化为一个不在数据范围的数                int n=scan.nextInt();                while(n-->0){                        String op=scan.next();                        int x=scan.nextInt();                        int k=find(x);                        if(op.equals("I")){                                h[k]=x;                        }                        else{                                if(h[k]!=INF) System.out.println("Yes");                                else System.out.println("No");                        }                }        }}

转载地址：http://cbuki.baihongyu.com/

你可能感兴趣的文章

docker上传镜像至Registry时https报错解决方法

Ubuntu 16.04开机A start job is running for Raise network interface(5min 4s)解决方法

查看>>

Ubuntu 16.04开机隐藏菜单缩短时间

查看>>