leetcode 1584. Min Cost to Connect All Points（python）

語言: CN / TW / HK
時間 2022-06-06 10:15:16

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第13天，點選檢視活動詳情

描述

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

Note:

1 <= points.length <= 1000
-10^6 <= xi, yi <= 10^6
All pairs (xi, yi) are distinct.

解析

根據題意，給定一個數組 points 表示 2D 平面上某些點的整數座標，其中 points[i] = [xi, yi]。 連線兩個點 [xi, yi] 和 [xj, yj] 的成本是它們之間的曼哈頓距離：|xi - xj| + |yi - yj|，其中 |val| 表示 val 的絕對值。 返回使所有點連線的最小成本。

這道題其實考察的是 Kruskal 演算法，因為要讓平面中兩個點之間的距離最短，且任意兩點之間只有一條路徑，最後的連線值儘可能小，能夠滿足任意兩點之間有且僅有一條權重路徑的只有最小生成樹，而最小生成樹有一個經典解法，就是 Kruskal 演算法 ，這是一個貪心演算法。

解答

class Solution(object):
    def minCostConnectPoints(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        dist = lambda x, y: abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1])

        n = len(points)
        dsu = DisjointSetUnion(n)
        edges = list()

        for i in range(n):
            for j in range(i + 1, n):
                edges.append((dist(i, j), i, j))

        edges.sort()

        ret, num = 0, 1
        for length, x, y in edges:
            if dsu.unionSet(x, y):
                ret += length
                num += 1
                if num == n:
                    break

        return ret

class DisjointSetUnion:
    def __init__(self, n):
        self.n = n
        self.rank = [1] * n
        self.f = list(range(n))

    def find(self, x):
        if self.f[x] == x:
            return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]

    def unionSet(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False

        if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx

        self.rank[fx] += self.rank[fy]
        self.f[fy] = fx
        return True

執行結果

Runtime: 3026 ms, faster than 59.86% of Python online submissions for Min Cost to Connect All Points.
Memory Usage: 80.9 MB, less than 68.03% of Python online submissions for Min Cost to Connect All Points.

原題連結

http://leetcode.com/problems/min-cost-to-connect-all-points/

您的支援是我最大的動力

「」
「」