文章目录
- 连接所有点的最小费用
- 思路一
连接所有点的最小费用
给你一个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示例 3：
输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4示例 4：
输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000示例 5：
输入：points = [[0,0]]
输出：0
思路一
function minCostConnectPoints(points) {const edges = [];const parents = new Array(points.length);let cost = 0;// 初始化并查集for (let i = 0; i < points.length; i++) {parents[i] = i;}// 计算所有边的权重for (let i = 0; i < points.length; i++) {for (let j = i + 1; j < points.length; j++) {const weight = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);edges.push([i, j, weight]);}}// 排序边的权重edges.sort((a, b) => a[2] - b[2]);// 查找并查集的根节点function find(node) {if (parents[node] !== node) {parents[node] = find(parents[node]);}return parents[node];}// 合并两个集合function union(x, y) {const rootX = find(x);const rootY = find(y);if (rootX !== rootY) {parents[rootX] = rootY;return true;}return false;}// Kruskal算法构建MSTfor (const [u, v, w] of edges) {if (union(u, v)) {cost += w;}}return cost;
}
讲解
这个问题可以看作是一个经典的最小生成树（Minimum Spanning Tree，MST）问题，但与传统的基于边权重的MST问题略有不同，因为边的权重（即曼哈顿距离）需要在运行时计算。为了解决这个问题，我们可以采用Prim算法或Kruskal算法，这里我们选择使用Kruskal算法，因为它不需要维护一个复杂的优先级队列，更适合于解决这种动态计算边权重的问题。
- 计算所有边的权重：遍历所有点对，计算它们之间的曼哈顿距离，并将这些边及其权重存储在一个数组中。
- 排序边的权重：将所有的边按照权重从小到大排序。
- Kruskal算法构建MST：
○ 使用并查集（Disjoint Set Union，DSU）数据结构来跟踪哪些顶点已经被包含在MST中，以及哪些顶点还处于分离状态。
○ 依次考虑排序后的每条边，如果这条边连接的两个顶点目前还没有在同一个集合中（即它们还没有被连接在一起），就将这条边添加到MST中，并将这两个顶点合并到同一个集合中。- 返回MST的总权重：当所有点都被包含在MST中时，累加所有被选中的边的权重，即为最小总费用。
