1584. Min Cost to Connect All Points
Tags:
Medium
Skills:
Union-FindPrim
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Approach - Kruskal (Union-Find)
Kruskal's Algorithm xây dựng MST bằng cách sắp xếp các cạnh theo thứ tự tăng dần của chi phí và thêm lần lượt vào cây khung nếu không tạo thành chu trình
Ý tưởng chính
Cách triển khai
Time and space complexity - Union Find
Solution - Union Find
1class UnionFind {
2 parent: number[];
3 rank: number[];
4
5 constructor(size: number) {
6 this.parent = Array.from({ length: size }, (_, i) => i);
7 this.rank = Array(size).fill(0);
8 }
9
10 find(node: number): number {
11 if (this.parent[node] !== node) {
12 this.parent[node] = this.find(this.parent[node])
13 }
14 return this.parent[node];
15 }
16
17 union(nodeA: number, nodeB: number): boolean {
18 const rootA = this.find(nodeA);
19 const rootB = this.find(nodeB);
20
21 if (rootA === rootB) return false;
22
23 if (this.rank[rootA] > this.rank[rootB]) {
24 this.parent[rootB] = rootA;
25 } else if (this.rank[rootA] < this.rank[rootB]) {
26 this.parent[rootA] = rootB;
27 } else {
28 this.parent[rootB] = rootA;
29 this.rank[rootA]++;
30 }
31
32 return true;
33 }
34}
35
36function minCostConnectPoints(points: number[][]): number {
37 const n = points.length;
38 const edges: [number, number, number][] = [];
39 for (let i = 0; i < n; i++) {
40 for (let j = i + 1; j < n; j++) {
41 const cost =
42 Math.abs(points[i][0] - points[j][0]) +
43 Math.abs(points[i][1] - points[j][1]);
44
45 edges.push([cost, i, j]);
46 }
47 }
48 edges.sort((a, b) => a[0] - b[0])
49
50 const uf = new UnionFind(n);
51 let total_cost = 0;
52 let edges_used = 0;
53 for (const [cost, u, v] of edges) {
54 if (uf.union(u, v)) {
55 total_cost += cost;
56 edges_used++;
57 if (edges_used === n - 1) break;
58 }
59 }
60
61 return total_cost
62};Giảm số lần lặp:
Solution - Prim
1function minCostConnectPoints(points: number[][]): number {
2 const n = points.length;
3 const visisted: boolean[] = new Array(n).fill(false);
4
5 const min_heap = new MinPriorityQueue(entry => entry[0])
6 let total_cost = 0;
7 let edges_used = 0;
8
9 min_heap.enqueue([0, 0])
10 while (edges_used < n) {
11 const [cost, curr_point] = min_heap.dequeue() as [number, number];
12 if (visisted[curr_point]) continue;
13
14 visisted[curr_point] = true;
15 total_cost += cost;
16 edges_used++;
17
18 for (let next_point = 0; next_point < n; next_point++) {
19 if (!visisted[next_point]) {
20 const next_cost = Math.abs(points[curr_point][0] - points[next_point][0]) +
21 Math.abs(points[curr_point][1] - points[next_point][1])
22
23 min_heap.enqueue([next_cost, next_point]);
24 }
25 }
26 }
27
28 return total_cost;
29}