Medium

题目描述

给你一个数组 points，表示 2D 平面上一些点的整数坐标，其中 points[i] = [xi, yi]。

连接两点 [xi, yi] 和 [xj, yj] 的费用是它们之间的 曼哈顿距离：|xi - xj| + |yi - yj|，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径。

示例 2：

输入：points = [[3,12],[-2,5],[-4,1]]
输出：18

提示：

  • 1 <= points.length <= 1000
  • -10^6 <= xi, yi <= 10^6
  • 所有点 (xi, yi) 两两不同。

解题思路

这是一个典型的最小生成树问题。我们需要连接所有点，使得总的连接费用最小。

解题思路

  1. 建图：将所有点视为图的节点，任意两点间的曼哈顿距离作为边权
  2. 最小生成树算法：可以使用 Kruskal 算法或 Prim 算法

Kruskal 算法（推荐）

  • 将所有边按权重排序
  • 使用并查集，依次选择权重最小的边
  • 如果该边连接的两点不在同一连通分量中，则选择这条边

Prim 算法

  • 从任意一点开始，维护一个最小堆
  • 每次选择连接已选点集合与未选点的最小权重边
  • 重复直到所有点都被包含

两种算法时间复杂度相同，但 Kruskal 实现相对简洁。对于本题的数据规模（n≤1000），两种方法都能高效解决。

代码实现

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<array<int, 3>> edges;
        
        // 构建所有边
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                edges.push_back({cost, i, j});
            }
        }
        
        // 按权重排序
        sort(edges.begin(), edges.end());
        
        // 并查集
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        int result = 0;
        int edgesUsed = 0;
        
        for (auto& edge : edges) {
            int cost = edge[0], u = edge[1], v = edge[2];
            int rootU = find(u), rootV = find(v);
            
            if (rootU != rootV) {
                parent[rootU] = rootV;
                result += cost;
                if (++edgesUsed == n - 1) break;
            }
        }
        
        return result;
    }
};

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        edges = []
        
        # 构建所有边
        for i in range(n):
            for j in range(i + 1, n):
                cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((cost, i, j))
        
        # 按权重排序
        edges.sort()
        
        # 并查集
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        result = 0
        edges_used = 0
        
        for cost, u, v in edges:
            root_u, root_v = find(u), find(v)
            
            if root_u != root_v:
                parent[root_u] = root_v
                result += cost
                edges_used += 1
                if edges_used == n - 1:
                    break
        
        return result

public class Solution {
    public int MinCostConnectPoints(int[][] points) {
        int n = points.Length;
        var edges = new List<(int cost, int u, int v)>();
        
        // 构建所有边
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = Math.Abs(points[i][0] - points[j][0]) + Math.Abs(points[i][1] - points[j][1]);
                edges.Add((cost, i, j));
            }
        }
        
        // 按权重排序
        edges.Sort();
        
        // 并查集
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        
        int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        int result = 0;
        int edgesUsed = 0;
        
        foreach (var (cost, u, v) in edges) {
            int rootU = Find(u), rootV = Find(v);
            
            if (rootU != rootV) {
                parent[rootU] = rootV;
                result += cost;
                if (++edgesUsed == n - 1) break;
            }
        }
        
        return result;
    }
}

var minCostConnectPoints = function(points) {
    const n = points.length;
    const edges = [];
    
    // 构建所有边
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
            edges.push([cost, i, j]);
        }
    }
    
    // 按权重排序
    edges.sort((a, b) => a[0] - b[0]);
    
    // 并查集
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        return parent[x]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度Kruskal算法
时间复杂度O(n²log n)
空间复杂度O(n²)

说明：

  • 时间复杂度：构建边需要 O(n²)，排序需要 O(n²log n)，并查集操作近似 O(n²α(n))，总体为 O(n²log n)
  • 空间复杂度：存储所有边需要 O(n²) 空间，并查集需要 O(n) 空间

相关题目