算法练习(90):quick-find(1.5.1)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：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

答案

详见分析

代码索引

QuickFind.java