-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathnumOfIslandII.java
More file actions
85 lines (78 loc) · 2.26 KB
/
numOfIslandII.java
File metadata and controls
85 lines (78 loc) · 2.26 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.*;
/** Weighted Union Find, 相比于num of islands I. 多了一个weighted 步骤，即争取保持树的平衡 **/
class UnionFind2{
int m,n;
int count = 0;
int[] id;
int[] size;
public UnionFind2(int row, int col){
m = row;
n = col;
id = new int[m*n];
Arrays.fill(id, -1);
size = new int[m*n];
}
// 这里就和num of islands I 不同
public void add(int x, int y){
int index = x * n + y;
id[index] = index;
size[index] = 1;
count ++;
}
public void union(int node1, int node2){
int find1 = find(node1);
int find2 = find(node2);
if(find1 == find2) return;
count --;
if(size[find1] > size[find2]){
id[find2] = find1;
size[find1] += size[find2];
}else{
id[find1] = find2;
size[find2] += size[find1];
}
}
public int getId(int i, int j){
if(i >= 0 && i < m && j >= 0 && j < n){
return id[i*n+j];
}
/** 越界或者此处不是'1'的时候返回0 **/
return -1;
}
/** find root **/
public int find(int node){
if(id[node] == node){
return node;
}
id[node] = find(id[node]);
return id[node];
}
}
public class numOfIslandII {
int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<>();
UnionFind2 UF2 = new UnionFind2(m,n);
for(int[] position:positions){
int x = position[0];
int y = position[1];
UF2.add(x,y);
for(int[] d : directions){
int i = x + d[0];
int j = y + d[1];
if(UF2.getId(i,j) >= 0){
int id1 = x * n + y;
int id2 = i * n + j;
UF2.union(id1, id2);
}
}
res.add(UF2.count);
}
return res;
}
public static void main(String[] args){
numOfIslandII obj = new numOfIslandII();
int[][] positions = {{0,0}, {0,1}, {1,2}, {2,1}};
System.out.println(obj.numIslands2(3,3, positions));
}
}