本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- 数组的访问次数
- quick-find 算法
题目
1.5.1 使用 quick-find 算法处理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。对于输入的每一对整数，给出 id[] 数组的内容和访问数组的次数。
1.5.1 Show the contents of the id[] array and the number of times the array is accessed for each input pair when you use quick-find for the sequence 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2.
分析
QuickFind的源代码如下：
public class QuickFind {
private int[] id; // access to component id (site indexed)
private int count; // number of components
public QuickFind(int N){
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
public int find(int p) {
return id[p];
}
public void union(int p, int q) { // Put p and q into the same component.
int pID = find(p);
int qID = find(q);
// Nothing to do if p and q are already in the same component.
if (pID == qID) return;
// Rename p’s component to q’s name.
for (int i = 0; i < id.length; i++)
if (id[i] == pID) id[i] = qID;
count--;
}
}
源码可在QuickFind.java找到。
测试用例如下：
public static void main(String[] args){
QuickFind find = new QuickFind(10);
find.union(9,0);
find.union(3,4);
find.union(5,8);
find.union(7,2);
find.union(2,1);
find.union(5,7);
find.union(0,3);
find.union(4,2);
}
然后我们再次审题：
给出 id[] 数组的内容和访问数组的次数
“给出 id[] 数组的内容”这个很好理解
那什么叫做“访问数组的次数”呢？仔细一想，我们不难发现获取数组内容，或者设置数组内容都算是一次“ 访问数组的次数”。因此，我们可以给QuickFind稍加改动，并用于计算访问数组的次数，代码如下：
public class QuickFind {
private int[] id; // access to component id (site indexed)
private int count; // number of components
//数组访问次数
int eachDoUnionArrayAccessTimes = 0;
public QuickFind(int N){
id = new int[N];
count = N;
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
public int find(int p) {
eachDoUnionArrayAccessTimes++;
return id[p];
}
public void union(int p, int q) { // Put p and q into the same component.
boolean printDetail = true;
if (printDetail) {
eachDoUnionArrayAccessTimes = 0;
System.out.println("开始联通分量"+p+"和"+q);
}
int pID = find(p);
int qID = find(q);
// Nothing to do if p and q are already in the same component.
if (pID == qID) return;
// Rename p’s component to q’s name.
for (int i = 0; i < id.length; i++)
{
eachDoUnionArrayAccessTimes++;
if (id[i] == pID)
{
eachDoUnionArrayAccessTimes++;
id[i] = qID;
}
}
count--;
/************************/
if (printDetail)
{
/***
* 以下代码输出数组元素
*/
System.out.print("id:{");
for (int i = 0; i < id.length; i++) {
if (i == id.length - 1) {
System.out.print(id[i]);
}else{
System.out.print(id[i] + ",");
}
}
System.out.print("}");
System.out.println("");
System.out.println("数组访问的次数:"+eachDoUnionArrayAccessTimes);
}
}
public static void main(String[] args){
QuickFind find = new QuickFind(10);
find.union(9,0);
find.union(3,4);
find.union(5,8);
find.union(7,2);
find.union(2,1);
find.union(5,7);
find.union(0,3);
find.union(4,2);
}
}
执行以上代码，我们可以得到如下打印结果：
开始联通分量9和0
id:{0,1,2,3,4,5,6,7,8,0}
数组访问的次数:13
开始联通分量3和4
id:{0,1,2,4,4,5,6,7,8,0}
数组访问的次数:13
开始联通分量5和8
id:{0,1,2,4,4,8,6,7,8,0}
数组访问的次数:13
开始联通分量7和2
id:{0,1,2,4,4,8,6,2,8,0}
数组访问的次数:13
开始联通分量2和1
id:{0,1,1,4,4,8,6,1,8,0}
数组访问的次数:14
开始联通分量5和7
id:{0,1,1,4,4,1,6,1,1,0}
数组访问的次数:14
开始联通分量0和3
id:{4,1,1,4,4,1,6,1,1,4}
数组访问的次数:14
开始联通分量4和2
id:{1,1,1,1,1,1,6,1,1,1}
数组访问的次数:16
答案
详见分析
