05 August 2008
A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
1
2
Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]
Explanation:
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
1
2
3
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1
2
3
1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1
2
3
1 1 0
0 0 0 Number of islands = 1
0 0 0
peration #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1
2
3
1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1
2
3
1 1 0
0 0 1 Number of islands = 3
0 1 0
Follow up:
Can you do it in time complexity O(k log mn), where k is the length of the positions?
暴力法是复用第200题Number of Islands的DFS代码，每添加一次就去查一下有多少个岛屿，时间复杂度O(L * m * n)，其中L是添加岛屿的次数。
这里要满足O(k logmn)的时间复杂度，依然用并查集的办法，每次添加岛屿后，求出连通图的个数，思路就是把2D数组当做一个无向图（以邻接矩阵的方式组织），横向或者纵向相邻的节点之间有一条值为 1 的边，那么问题就变成了每次 addLand 操作之后在图中寻找连通部分的问题。
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
class Solution {
private int[][] dir = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
public List<Integer> numIslands2(int m, int n, int[][] positions) {
UnionFind2D islands = new UnionFind2D(m, n);
List<Integer> results = new ArrayList<>();
for (int[] position : positions) {
int x = position[0], y = position[1];
int positionIndex = islands.getID(x, y);
if (positionIndex == 0) {
int p = islands.add(x, y);
for (int[] d : dir) {
int q = islands.getID(x + d[0], y + d[1]);
if (q > 0 && !islands.find(p, q)) {
islands.unite(p, q);
}
}
}
results.add(islands.size());
}
return results;
}
}
// 以下是并查集的模板
class UnionFind2D {
private int[] id;
private int[] sz;
private int m, n, count;
public UnionFind2D(int m, int n) {
this.count = 0;
this.n = n;
this.m = m;
this.id = new int[m * n + 1];
this.sz = new int[m * n + 1];
}
public int index(int x, int y) { return x * n + y + 1; }
public int size() { return this.count; }
public int getID(int x, int y) {
if (0 <= x && x < m && 0<= y && y < n)
return id[index(x, y)];
return 0;
}
public int add(int x, int y) {
int i = index(x, y);
id[i] = i; sz[i] = 1;
++count;
return i;
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
public void unite(int p, int q) {
int i = root(p), j = root(q);
if (sz[i] < sz[j]) { //weighted quick union
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
count--;
}
private int root(int i) {
for (;i != id[i]; i = id[i])
id[i] = id[id[i]]; //并查集的path compression
return i;
}
}