当前位置:网站首页>LeetCode 1584. Minimum cost of connecting all points
LeetCode 1584. Minimum cost of connecting all points
2022-07-06 16:43:00 【Daylight629】
1584. The minimum cost of connecting all points
To give you one points
Array , Express 2D Some points on the plane , among points[i] = [xi, yi]
.
Connection point [xi, yi]
Sum point [xj, yj]
The cost is between them Manhattan distance :|xi - xj| + |yi - yj|
, among |val|
Express val
The absolute value of .
Please return the minimum total cost of connecting all points . Just between any two points Yes and no A simple path , All the points are connected .
Example 1:
Input :points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output :20
explain :
We can connect all the points as shown in the figure above to get the minimum total cost , The total cost is 20 .
Notice that there is only one path between any two points to reach each other .
Example 2:
Input :points = [[3,12],[-2,5],[-4,1]]
Output :18
Example 3:
Input :points = [[0,0],[1,1],[1,0],[-1,1]]
Output :4
Example 4:
Input :points = [[-1000000,-1000000],[1000000,1000000]]
Output :4000000
Example 5:
Input :points = [[0,0]]
Output :0
Tips :
1 <= points.length <= 1000
-106 <= xi, yi <= 106
- All points
(xi, yi)
Two are different .
Two 、 Method 1
Kruskal Algorithm
class Solution {
public 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, new Comparator<Edge>() {
public int compare(Edge edge1, Edge edge2) {
return edge1.len - edge2.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 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]);
}
}
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;
}
}
public int find(int x) {
return f[x] == x ? x : (f[x] = find(f[x]));
}
public boolean unionSet(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) {
return false;
}
if (rank[fx] < rank[fy]) {
int temp = fx;
fx = fy;
fy = temp;
}
rank[fx] += rank[fy];
f[fy] = fx;
return true;
}
}
class Edge {
int len, x, y;
public Edge(int len, int x, int y) {
this.len = len;
this.x = x;
this.y = y;
}
}
Complexity analysis
Time complexity :O(n2 log(n)), among n It's the number of nodes . commonly Kruskal yes O(mlogm) The algorithm of , But in this question m=n^2
, So the total time complexity is O(n2log(n)).Spatial complexity :O(n^2), among n It's the number of nodes . Use of parallel search set O(n) Space , The edge set array needs to use O(n^2) Space .
边栏推荐
- Kubernetes集群部署
- Installation and configuration of MariaDB
- Date plus 1 day
- Market trend report, technical innovation and market forecast of China's desktop capacitance meter
- Chapter 6 datanode
- Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
- Bidirectional linked list - all operations
- Generate random password / verification code
- 第一章 MapReduce概述
- Simple records of business system migration from Oracle to opengauss database
猜你喜欢
Detailed explanation of FLV format
Chapter 2 shell operation of hfds
顺丰科技智慧物流校园技术挑战赛(无t4)
Solve the single thread scheduling problem of intel12 generation core CPU (II)
js封装数组反转的方法--冯浩的博客
One hundred questions of image processing (11-20)
Mp4 format details
Chapter III principles of MapReduce framework
Chapter 7__ consumer_ offsets topic
Problem - 922D、Robot Vacuum Cleaner - Codeforces
随机推荐
Codeforces Round #771 (Div. 2)
第7章 __consumer_offsets topic
China tetrabutyl urea (TBU) market trend report, technical dynamic innovation and market forecast
The concept of spark independent cluster worker and executor
Summary of FTP function implemented by qnetworkaccessmanager
我在字节跳动「修电影」
Market trend report, technical innovation and market forecast of China's desktop capacitance meter
Li Kou leetcode 280 weekly match
300th weekly match - leetcode
Click QT button to switch qlineedit focus (including code)
Chapter 6 datanode
Input can only input numbers, limited input
China double brightening film (dbef) market trend report, technical dynamic innovation and market forecast
音视频开发面试题
Use JQ to realize the reverse selection of all and no selection at all - Feng Hao's blog
图像处理一百题(11-20)
(lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
(lightoj - 1323) billiard balls (thinking)
拉取分支失败,fatal: ‘origin/xxx‘ is not a commit and a branch ‘xxx‘ cannot be created from it
One hundred questions of image processing (11-20)