LeetCode 1584. Minimum cost of connecting all points

1584. The minimum cost of connecting all points

To give you one points Array , Express 2D Some points on the plane , among points[i] = [xi, yi] .

Connection point [xi, yi] Sum point [xj, yj] The cost is between them Manhattan distance ：|xi - xj| + |yi - yj| , among |val| Express val The absolute value of .

Please return the minimum total cost of connecting all points . Just between any two points Yes and no A simple path , All the points are connected .

Example 1：

 Input ：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
 Output ：20
 explain ：

 We can connect all the points as shown in the figure above to get the minimum total cost , The total cost is  20 .
 Notice that there is only one path between any two points to reach each other .

Example 2：

 Input ：points = [[3,12],[-2,5],[-4,1]]
 Output ：18

Example 3：

 Input ：points = [[0,0],[1,1],[1,0],[-1,1]]
 Output ：4

Example 4：

 Input ：points = [[-1000000,-1000000],[1000000,1000000]]
 Output ：4000000

Example 5：

 Input ：points = [[0,0]]
 Output ：0

Tips ：

• 1 <= points.length <= 1000
• -106 <= xi, yi <= 106
• All points (xi, yi) Two are different .

Two 、 Method 1

Kruskal Algorithm

class Solution {
    
    public int minCostConnectPoints(int[][] points) {
    
        int n = points.length;
        DisjointSetUnion dsu = new DisjointSetUnion(n);
        List<Edge> edges = new ArrayList<Edge>();
        for (int i = 0; i < n; i++) {
    
            for (int j = i + 1; j < n; j++) {
    
                edges.add(new Edge(dist(points, i, j), i, j));
            }
        }
        Collections.sort(edges, new Comparator<Edge>() {
    
            public int compare(Edge edge1, Edge edge2) {
    
                return edge1.len - edge2.len;
            }
        });
        int ret = 0, num = 1;
        for (Edge edge : edges) {
    
            int len = edge.len, x = edge.x, y = edge.y;
            if (dsu.unionSet(x, y)) {
    
                ret += len;
                num++;
                if (num == n) {
    
                    break;
                }
            }
        }
        return ret;
    }

    public int dist(int[][] points, int x, int y) {
    
        return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
    }
}

class DisjointSetUnion {
    
    int[] f;
    int[] rank;
    int n;

    public DisjointSetUnion(int n) {
    
        this.n = n;
        this.rank = new int[n];
        Arrays.fill(this.rank, 1);
        this.f = new int[n];
        for (int i = 0; i < n; i++) {
    
            this.f[i] = i;
        }
    }

    public int find(int x) {
    
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

    public boolean unionSet(int x, int y) {
    
        int fx = find(x), fy = find(y);
        if (fx == fy) {
    
            return false;
        }
        if (rank[fx] < rank[fy]) {
    
            int temp = fx;
            fx = fy;
            fy = temp;
        }
        rank[fx] += rank[fy];
        f[fy] = fx;
        return true;
    }
}

class Edge {
    
    int len, x, y;

    public Edge(int len, int x, int y) {
    
        this.len = len;
        this.x = x;
        this.y = y;
    }
}

Complexity analysis

• Time complexity ：O(n2 log(n)), among n It's the number of nodes . commonly Kruskal yes O(mlogm) The algorithm of , But in this question m=n^2
  , So the total time complexity is O(n2log(n)).

• Spatial complexity ：O(n^2), among n It's the number of nodes . Use of parallel search set O(n) Space , The edge set array needs to use O(n^2) Space .