README_EN.md

1584. Min Cost to Connect All Points

中文文档

Description

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

 

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

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

 

Constraints:

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

Solutions

Python3

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        p = list(range(n))

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        edges = []
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                edges.append([abs(x1 - x2) + abs(y1 - y2), i, j])
        edges.sort()
        res = 0
        for cost, i, j in edges:
            if find(i) == find(j):
                continue
            p[find(i)] = find(j)
            n -= 1
            res += cost
            if n == 1:
                return res
        return 0

Java

class Solution {
    private int[] p;
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j =  i + 1; j < n; ++j) {
                int x2 = points[j][0], y2 = points[j][1];
                edges.add(new int[]{Math.abs(x1 - x2) + Math.abs(y1 - y2), i, j});
            }
        }
        edges.sort(Comparator.comparingInt(a -> a[0]));
        int res = 0;
        for (int[] e : edges) {
            if (find(e[1]) == find(e[2])) {
                continue;
            }
            p[find(e[1])] = find(e[2]);
            --n;
            res += e[0];
            if (n == 1) {
                break;
            }
        }
        return res;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

C++

class Solution {
public:
    vector<int> p;

    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        p.resize(n);
        for (int i = 0; i < n; ++i) p[i] = i;
        vector<vector<int>> edges;
        for (int i = 0; i < n; ++i)
        {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = i + 1; j < n; ++j)
            {
                int x2 = points[j][0], y2 = points[j][1];
                edges.push_back({abs(x1 - x2) + abs(y1 - y2), i, j});
            }
        }
        sort(edges.begin(), edges.end());
        int res = 0;
        for (auto e : edges)
        {
            if (find(e[1]) == find(e[2])) continue;
            p[find(e[1])] = find(e[2]);
            --n;
            res += e[0];
            if (n == 1) break;
        }
        return res;
    }

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
};

Go

var p []int

func minCostConnectPoints(points [][]int) int {
    n := len(points)
    p = make([]int, n)
    for i := 0; i < n; i++ {
        p[i] = i
    }
    var edges [][]int
    for i := 0; i < n; i++ {
        x1, y1 := points[i][0], points[i][1]
        for j := i + 1; j < n; j++ {
            x2, y2 := points[j][0], points[j][1]
            edges = append(edges, []int{abs(x1 - x2) + abs(y1 - y2), i, j})
        }
    }
    sort.Slice(edges, func(i, j int) bool {
        return edges[i][0] < edges[j][0]
    })
    res := 0
    for _, e := range edges {
        if find(e[1]) == find(e[2]) {
            continue
        }
        p[find(e[1])] = find(e[2])
        n--
        res += e[0]
        if n == 1 {
            break
        }
    }
    return res
}

func find(x int) int {
    if p[x] != x {
        p[x] = find(p[x])
    }
    return p[x]
}

func abs(x int) int {
    if x > 0 {
        return x
    }
    return -x
}

...