题目描述
给你一个 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 。
注意到任意两个点之间只有唯一一条路径互相到达。
提示：
- 1 <= points.length <= 1000
- -106 <= xi, yi <= 106
- 所有点 (xi, yi) 两两不同。
写在前面
根据题目要求，我们可以用points数组构建一张节点为n的连通图，任意两点之间的距离均为它们的曼哈顿距离，我们需要在这个图中获取一个极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的总权值最小。
能够满足任意两点之间有且仅有一条简单路径只有树，且这棵树包含 nn 个节点。我们称这棵树为给定的图的生成树，其中总权值最小的生成树，我们称其为最小生成树。若不懂最小生成树的同学可以我写的另一篇文章数据结构-最小生成树
最小生成树有两个非常经典的解法：Kruskal 和 Prim
方法一：Kruskal 算法
class Solution {
class UnionFind {
private int[] parent;
public UnionFind(int N) {
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
}
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
while (p != parent[p]) {
p = find(parent[p]);
}
return parent[p];
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
}
}
private static class Edge {
int v, e, w;
public Edge(int v, int e, int w) {
this.v = v;
this.e = e;
this.w = w;
}
}
public int minCostConnectPoints(int[][] points) {
Queue<Edge> mst = new LinkedList<>();
Queue<Edge> pq = new PriorityQueue<>((a, b) -> {
return a.w - b.w;
});
int res = 0;
int n = points.length;
for (int i = 0; i < n; ++i) {
for (int j = 0; j != i && j < n; ++j) {
pq.offer(new Edge(i, j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])));
}
}
UnionFind uf = new UnionFind(n);
while (!pq.isEmpty()) {
Edge cur = pq.poll();
if (!uf.connected(cur.v, cur.e)) {
mst.offer(cur);
uf.union(cur.v, cur.e);
}
}
while (!mst.isEmpty()) {
Edge e = mst.poll();
res += e.w;
}
return res;
}
}
原题链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points/
评论