1584 连接所有点的最小费用
给你一个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
提示：
1 <= points.length <= 1000
-106 <= xi, yi <= 106
所有点 (xi, yi) 两两不同。
package com.example.lettcode.dailyexercises;
import java.util.Arrays;
import java.util.Comparator;
/**
* @Class MinCostConnectPoints
* @Description 1584 连接所有点的最小费用
* @Author
* @Date 2021/1/19
**/
public class MinCostConnectPoints {
private static class Edge {
int p1;
int p2;
int distance;
public Edge(int p1, int p2, int distance) {
this.p1 = p1;
this.p2 = p2;
this.distance = distance;
}
}
/**
* 找到target在并查集中对应的root节点
*
* @param target
* @param rec
* @return
*/
public static int find(int target, int[] rec) {
int root = target;
/**
* 一层一层向上找到所对应的根节点
*/
while (root != rec[root]) {
root = rec[root];
}
// 更新并查集
int cur = target;
while (cur != rec[cur]) {
rec[cur] = root;
cur = rec[cur];
}
return root;
}
/**
* 判断两个点的根是否相同，不同则表示没有连接在树内
*
* @param p1
* @param p2
* @param rec 并查集，对于每个点都记录其对应的root节点
* @return
*/
public static boolean union(int p1, int p2, int[] rec) {
int rootP1 = find(p1, rec);
int rootP2 = find(p2, rec);
rec[rootP1] = rootP2;// 两个根节点指向一起
return rootP1 == rootP2;
}
/**
* 克鲁斯卡尔算法
*
* @param points
* @return
*/
public static int kruskal(int[][] points) {
int length = points.length;
Edge[] edges = new Edge[length * length];
// 初始化距离数组
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
// 计算出两点之间的距离
int distance = i == j ? Integer.MAX_VALUE : Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
// 初始化距离数组
edges[i * length + j] = new Edge(i, j, distance);
}
}
// 根据距离进行排序
Arrays.sort(edges, new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.distance - o2.distance;
}
});
// 初始化并查集数组
int[] rec = new int[length];
for (int i = 0; i < length; i++) {
rec[i] = i;
}
int count = 0;
int cost = 0;
for (int i = 0; i < edges.length && count < length - 1; i++) {
Edge edge = edges[i];
int p1 = edge.p1;
int p2 = edge.p2;
if (union(p1, p2, rec) == false) {
++count;
cost += edge.distance;
}
}
return cost;
}
public static int minCostConnectPoints(int[][] points) {
return kruskal(points);
}
}
// 测试用例
public static void main(String[] args) {
int[][] points = new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
int ans = minCostConnectPoints(points);
System.out.println("MinCostConnectPoints demo01 result:" + ans);
points = new int[][]{{3, 12}, {-2, 5}, {-4, 1}};
ans = minCostConnectPoints(points);
System.out.println("MinCostConnectPoints demo02 result:" + ans);
points = new int[][]{{0, 0}, {1, 1}, {1, 0}, {-1, 1}};
ans = minCostConnectPoints(points);
System.out.println("MinCostConnectPoints demo03 result:" + ans);
points = new int[][]{{-1000000, -1000000}, {1000000, 1000000}};
ans = minCostConnectPoints(points);
System.out.println("MinCostConnectPoints demo04 result:" + ans);
points = new int[][]{{0, 0}};
ans = minCostConnectPoints(points);
System.out.println("MinCostConnectPoints demo05 result:" + ans);
}