【每日一题】 1584. 连接所有点的最小费用

淩亂°似流年 2023-01-09 12:31 131阅读 0赞

# 【每日一题】 1584. 连接所有点的最小费用 #

> 避免每日太过咸鱼，一天搞定一道LeetCode算法题

## 一、题目描述 ##

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

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

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

**提示：**

*  `1 <= points.length <= 1000`
 *  `-106 <= xi, yi <= 106`
 *  所有点 `(xi, yi)` 两两不同。

**示例 1：**  
![在这里插入图片描述][20210121091443514.png_pic_center]

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
    输出：20

**解释：**

![在这里插入图片描述][20210121092619965.png_pic_center]

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。  
注意到任意两个点之间只有唯一一条路径互相到达。

**示例 2：**

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

**示例 3：**

输入：points = [[0,0],[1,1],[1,0],[-1,1]]
    输出：4

**示例 4：**

输入：points = [[-1000000,-1000000],[1000000,1000000]]
    输出：4000000

**示例 5：**

输入：points = [[0,0]]
    输出：0

## 二、题解 ##

### 1. 解法 ###

根据题意，我们得到了一张 n 个节点的完全图，任意两点之间的距离均为它们的曼哈顿距离。现在我们需要在这个图中取得一个子图，恰满足子图的任意两点之间有且仅有一条简单路径，且这个子图的所有边的总权值之和尽可能小。

能够满足任意两点之间有且仅有一条简单路径只有树，且这棵树包含 n 个节点。我们称这棵树为给定的图的生成树，其中总权值最小的生成树，我们称其为最小生成树。

最小生成树有一个非常经典的解法：[Kruskal][] 。

### 1. 解法 ###

**解题思路：**

Kruskal 算法是一种常见并且好写的最小生成树算法，由 [Kruskal][] 发明。该算法的基本思想是从小到大加入边，是一个贪心算法。

其算法流程为：

将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

在实际代码中，我们首先将这张完全图中的边全部提取到边集数组中，然后对所有边进行排序，从小到大进行枚举，每次贪心选边加入答案。使用并查集维护连通性，若当前边两端不连通即可选择这条边。

**java代码实现如下：**

public static 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, Comparator.comparingInt(edge -> edge.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 static 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]);
    }
    
    static 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;
            }
        }
    
        /** * 找到传入x节点的root节点 * * @param x 顶点 * @return root节点 */
        public int find(int x) { 
            return f[x] == x ? x : (f[x] = find(f[x]));
        }
    
        /** * 判断传入的顶点是否在图中形成回路 */
        public boolean unionSet(int x, int y) { 
            // 找到 x y 的根节点位置 fx fy
            int fx = find(x), fy = find(y);
            // 如果fx = fy 就是同一个根节点 直接返回false
            if (fx == fy) { 
                return false;
            }
    
            if (rank[fx] < rank[fy]) { 
                // 进来代表根节点是fy 为了方便后面rank路径压缩 和 指向root节点 所以交换 fx fy
                int temp = fx;
                fx = fy;
                fy = temp;
            }
            // 选定第一次过来的 fx 为根节点
            rank[fx] += rank[fy];
            // 将fy的位置指向根节点
            f[fy] = fx;
            return true;
        }
    }
    
    static class Edge { 
        int len, x, y;
    
        public Edge(int len, int x, int y) { 
            this.len = len;
            this.x = x;
            this.y = y;
        }
    }

**复杂度分析**

*  时间复杂度：*O*(*n*^2 log(*n*))，其中 n 是节点数。一般 Kruskal 是 O(mlog m)的算法，但本题中 m=n^2 ，因此总时间复杂度为 *O*(*n*^2 log(*n*))。
 *  空间复杂度：*O*(*n*^2)，其中 n是节点数。并查集使用 O(n)的空间，边集数组需要使用 O(n^2)的空间。

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distance-between-bus-stops

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[20210121091443514.png_pic_center]: /images/20221119/5c00d5e609474092aaf431ed459ef4a6.png
[20210121092619965.png_pic_center]: /images/20221119/a148063b0d9743ec99268d8786c104a7.png
[Kruskal]: https://blog.csdn.net/Zack_tzh/article/details/112903512
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221119/f9bf9121e5314dd58425bda2f9ffa44d.png