|
1 | 1 | classSolution { |
2 | | -publicintminCostConnectPoints(int[][]points) { |
3 | | -intn =points.length; |
4 | | -PriorityQueue<Edge>priorityQueue =newPriorityQueue<>((x,y) ->x.cost -y.cost); |
5 | | -UnionFindunionFind =newUnionFind(n); |
6 | | -for (inti =0;i <n;i++) { |
7 | | -int[]coordinate =points[i]; |
8 | | -for (intj =i +1;j <n;j++) { |
9 | | -int[]secondCoordinate =points[j]; |
10 | | -intcost =Math.abs(coordinate[0] -secondCoordinate[0]) +Math.abs(coordinate[1] -secondCoordinate[1]); |
11 | | -Edgeedge =newEdge(i,j,cost); |
12 | | -priorityQueue.add(edge); |
13 | | - } |
14 | | - } |
15 | | -intminimumCost =0; |
16 | | -inttotalEdges =n -1; |
17 | | -while (!priorityQueue.isEmpty() &&totalEdges >0) { |
18 | | -Edgeedge =priorityQueue.poll(); |
19 | | -if (!unionFind.connected(edge.pointOne,edge.pointTwo)) { |
20 | | -unionFind.union(edge.pointOne,edge.pointTwo); |
21 | | -minimumCost +=edge.cost; |
22 | | -totalEdges--; |
23 | | - } |
24 | | - } |
25 | | -returnminimumCost; |
26 | | - } |
27 | | - |
28 | | -privatestaticclassEdge { |
29 | | -intpointOne; |
30 | | -intpointTwo; |
31 | | -intcost; |
32 | | - |
33 | | -publicEdge(intpointOne,intpointTwo,intcost) { |
34 | | -this.pointOne =pointOne; |
35 | | -this.pointTwo =pointTwo; |
36 | | -this.cost =cost; |
| 2 | +publicintminCostConnectPoints(int[][]points) { |
| 3 | +intn =points.length; |
| 4 | +List<int[]>edges =newArrayList<>(); |
| 5 | +for (inti =0;i <n;i++) { |
| 6 | +for (intj =i +1;j <n;j++) { |
| 7 | +intweight =Math.abs(points[i][0] -points[j][0]) +Math.abs(points[i][1] -points[j][1]); |
| 8 | +int[]curr = {weight,i,j}; |
| 9 | +edges.add(curr); |
| 10 | + } |
| 11 | + } |
| 12 | +Collections.sort(edges,Comparator.comparingInt(a ->a[0])); |
| 13 | +UnionFindunionFind =newUnionFind(n); |
| 14 | +intminCost =0; |
| 15 | +intedgeUsedCount =0; |
| 16 | +for (inti =0;i <edges.size() &&edgeUsedCount <n -1;i++) { |
| 17 | +intnodeOne =edges.get(i)[1]; |
| 18 | +intnodeTwo =edges.get(i)[2]; |
| 19 | +intweight =edges.get(i)[0]; |
| 20 | +if (unionFind.union(nodeOne,nodeTwo)) { |
| 21 | +minCost +=weight; |
| 22 | +edgeUsedCount++; |
| 23 | + } |
| 24 | + } |
| 25 | +returnminCost; |
37 | 26 | } |
38 | | - } |
39 | | - |
40 | | -privatestaticclassUnionFind { |
41 | 27 |
|
42 | | -privatefinalint[]root; |
43 | | -privatefinalint[]rank; |
| 28 | +privatestaticclassUnionFind { |
| 29 | +privatefinalint[]group; |
| 30 | +privatefinalint[]rank; |
44 | 31 |
|
45 | | -publicUnionFind(intsize) { |
46 | | -this.root =newint[size]; |
47 | | -this.rank =newint[size]; |
48 | | -for (inti =0;i <size;i++) { |
49 | | -this.root[i] =i; |
50 | | -this.rank[i] =1; |
51 | | - } |
52 | | - } |
53 | | - |
54 | | -publicvoidunion(intnodeOne,intnodeTwo) { |
55 | | -introotOne =find(nodeOne); |
56 | | -introotTwo =find(nodeTwo); |
57 | | -if (rootOne !=rootTwo) { |
58 | | -if (this.rank[rootOne] >this.rank[rootTwo]) { |
59 | | -this.root[rootTwo] =rootOne; |
60 | | - }elseif (this.rank[rootOne] <this.rank[rootTwo]) { |
61 | | -this.root[rootOne] =rootTwo; |
62 | | - }else { |
63 | | -this.root[rootTwo] =rootOne; |
64 | | -this.rank[rootOne]++; |
| 32 | +publicUnionFind(intn) { |
| 33 | +this.group =newint[n]; |
| 34 | +this.rank =newint[n]; |
| 35 | +for (inti =0;i <n;i++) { |
| 36 | +this.group[i] =i; |
| 37 | + } |
65 | 38 | } |
66 | | - } |
67 | | - } |
68 | 39 |
|
69 | | -publicintfind(intnode) { |
70 | | -if (node ==root[node]) { |
71 | | -returnnode; |
72 | | - } |
73 | | -returnroot[node] =find(root[node]); |
74 | | - } |
| 40 | +publicintfind(intnode) { |
| 41 | +if (group[node] !=node) { |
| 42 | +group[node] =find(group[node]); |
| 43 | +} |
| 44 | +returngroup[node]; |
| 45 | +} |
75 | 46 |
|
76 | | -publicbooleanconnected(intnodeOne,intnodeTwo) { |
77 | | -returnfind(nodeOne) ==find(nodeTwo); |
| 47 | +publicbooleanunion(intnodeOne,intnodeTwo) { |
| 48 | +intgroupOne =find(nodeOne); |
| 49 | +intgroupTwo =find(nodeTwo); |
| 50 | +if (groupOne ==groupTwo) { |
| 51 | +returnfalse; |
| 52 | + } |
| 53 | +if (rank[groupOne] >rank[groupTwo]) { |
| 54 | +group[groupTwo] =groupOne; |
| 55 | + }elseif (rank[groupOne] <rank[groupTwo]) { |
| 56 | +group[groupOne] =groupTwo; |
| 57 | + }else { |
| 58 | +group[groupOne] =groupTwo; |
| 59 | +rank[groupTwo]++; |
| 60 | + } |
| 61 | +returntrue; |
| 62 | + } |
78 | 63 | } |
79 | | - } |
80 | 64 | } |