文章目录
题目拉链法算法说明变量定义源代码经验总结
开放寻址法算法说明变量定义源代码代码说明
题目
维护一个集合，支持如下几种操作： “I x”，插入一个数x； “Q x”，询问数x是否在集合中出现过； 现在要进行N次操作，对于每个询问操作输出对应的结果。 输入格式 第一行包含整数N，表示操作数量。 接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。 输出格式 对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。 每个结果占一行。 数据范围 1≤N≤105 −109≤x≤109
输入样例：
5 I 1 I 2 I 3 Q 2 Q 5
输出样例：
Yes No
拉链法算法说明
拉链法算法是散列表的经典算法之一.首先明确,散列表(hash表)到底是如何存储/查找数据的. 本质上来说,散列表是将一个大的空间通过某种算法映射到一个小的空间,这样在查找时,可以快速的找到目标,相当于为每一个人单独定了一个房间,只要给出名字立马就可以找到对应的房间,而不用一个个遍历. 就好比 刘一住在"刘氏房间",李二住在"李氏房间"等等,想找刘一直接去刘氏房间即可,不用挨个房间走寻找了.如果有多个姓刘的呢?那么他们一定会都住在刘氏房间,我们只要在刘氏房间,按照链表的形式就能找到了. 这个,就是拉链法的思想.
变量定义
拉链法需要定义以下几个变量(以后的算法文章都要列出此算法需要定义哪些变量,含义是什么)
h[]:代表"房间",真正的含义是链表的头指针,因此我们将英文定为h,并初始化为0e[index]:代表index结点的值ne[index]:代表index结点的下一结点的指针index:代表结点的编号,新建结点的编号从1开始,这样头指针指向0就表示没有任何的结点. e[index]如同之前的链表的含义,新节点的出现就是此数组的新索引的赋值.
源代码
import java
.util
.*
;
class Main{
static int N
=100010;
static int index
;
static int[] e
=new int[N
];
static int[] ne
=new int[N
];
static int[] h
=new int[N
];
public static void main(String
[] args
){
int index
=0;
Scanner sc
=new Scanner(System
.in
);
int n
=sc
.nextInt();
sc
.nextLine();
while(n
-->0){
String
[] s
=sc
.nextLine().split(" ");
if("I".equals(s
[0])){
int x
=Integer
.parseInt(s
[1]);
insert(x
);
}
else{
int x
=Integer
.parseInt(s
[1]);
String res
=seek(x
);
System
.out
.println(res
);
}
}
}
public static void insert(int x
){
int k
=change2hash(x
);
index
++;
e
[index
]=x
;
ne
[index
]=h
[k
];
h
[k
]=index
;
}
public static String
seek(int x
){
int k
=change2hash(x
);
int idx
=h
[k
];
while(idx
!=0){
if(e
[idx
]==x
) return "Yes";
else idx
=ne
[idx
];
}
return "No";
}
public static int change2hash(int x
){
return (x
%N
+N
)%N
;
}
}
经验总结
由于java不存在指针传递,因此为了让值通过函数修改,我们需要让变量设为static,这样就绕过了传入形参的过程,我们也无需思考传入形参的过程,直接对变量本身进行修改.
开放寻址法算法说明
开放寻址法和拉链法都是在给出目标时,可以立马将大的搜索域变为小的搜索域.不同的是,开放寻址法没有使用纵向链表结构,而是使用横向的继续搜索方式.在定位位置没有找到则会继续跳向下一个位置,直到搜索到或者遍历一遍为止.搜索存在的元素速度会很快(搜索没有的元素会遍历所有)
变量定义
h[k]:存储k位置的值(直接就是值了)NULL:因为数组存储的直接就是值,而在插入/寻找时要确定当前位置有没有被插入过,此时未插入的值就不能像头结点那个选为-1或者0了,因为很可能插入的就是-1/0,为防止此情况,选用值范围外的数字定位NULL,并在数组初始化时全部初始化为NULL
源代码
import java
.util
.*
;
class Main{
static int N
=100010;
static int index
;
static int NULL
=0x3f3f3f;
static int[] h
=new int[N
];
public static void main(String
[] args
){
Scanner sc
=new Scanner(System
.in
);
for(int i
=0;i
<N
;i
++){
h
[i
]=NULL
;
}
int n
=sc
.nextInt();
sc
.nextLine();
while(n
-->0){
String
[] s
=sc
.nextLine().split(" ");
if("I".equals(s
[0])){
int x
=Integer
.parseInt(s
[1]);
int k
=find(x
);
h
[k
]=x
;
}
else{
int x
=Integer
.parseInt(s
[1]);
int k
=find(x
);
String s1
;
if(h
[k
]==x
) s1
="Yes";
else s1
="No";
System
.out
.println(s1
);
}
}
}
public static 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
;
}
}
代码说明
对于此代码,最重要的是find函数,表示的含义是数值x应该存储的位置,这样插入时在此位置插入,寻找时在此位置寻找即可. 另外值得注意的是,开放寻址的数组范围一般会是数的3倍,因此不会存在无限循环查找的情况了. 也就是不需要担心
while(h
[k
]!=NULL
&&h
[k
]!=x
){
k
++;
if(k
==N
){
k
=0;
}
}
会死循环
