时间戳

首页 > 解决方案 > Leetcode 1584. 如何改进我的 Kruskal&Union Find 算法以使其更快？

java - Leetcode 1584. 如何改进我的 Kruskal&Union Find 算法以使其更快？

问题描述

问题出在 Leetcode 1584。连接所有点的最低成本。我对这个问题的回答是：

class Solution {
    public int minCostConnectPoints(int[][] points) {
        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < points.length; i++){
            for(int j = 0; j < points.length; j++){
                int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                list.add(new int[]{i,j,dist});
            }
        }
        list.sort((int a[], int b[]) -> a[2] - b[2]);
        UnionFindSet uf = new UnionFindSet(points.length);
        int totalCost = 0;
        for(int edges[] : list){
            if(uf.Find(edges[0]) != uf.Find(edges[1])){
                uf.Union(edges[0],edges[1]);
                totalCost += edges[2];
            }
        }
        return totalCost;
    }
}

class UnionFindSet {
    public final int[] parents;

    UnionFindSet(int size) {
        this.parents = new int[size];
        for (int i = 0; i < size; i++) {
            this.parents[i] = i;
        }
    }

    public int Find(int x) {
        if (this.parents[x] != x) {
            this.parents[x] = Find(this.parents[x]);
        }
        return this.parents[x];
    }

    public void Union(int x, int y) {
        this.parents[Find(y)] = Find(x);
    }
}

我的答案可以通过所有测试用例，但速度极慢。知道如何改进我的代码以使其更快吗？我的一个猜测可能是计算曼哈顿距离的嵌套 for 循环很昂贵，但我不知道如何省略或替换它。任何想法将不胜感激！

标签： javaalgorithmminimum-spanning-treekruskals-algorithmunion-find

解决方案

您UnionFindSet需要按大小或等级进行路径压缩和联合。它们在维基百科文章中得到了很好的解释：https ://en.wikipedia.org/wiki/Disjoint-set_data_structure

它们也不难实施。我在这里用python实现了：如何正确实现不相交的集合数据结构以在Python中查找跨越森林？

推荐阅读