305 Number of Islands II
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:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
.
Initially, the 2d grid grid
is filled with water. (Assume 0 represents water and 1 represents land).
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 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 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
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 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
Challenge:
Can you do it in time complexity O(k log mn), where k is the length of the positions
?
分析& 代码
使用Union-Find方法。
应该还是比较标准的uf,但是开始自己看不出来。把二维压成一维,给一个编号,其他的基本上没有变化。
伪代码解释:
对于每一个新加的点:
cnt++;
//uf做的部分就是把连起来了的岛融合在一起,调整这个cnt的
把自己的parent标记成自己
对于每一个方向:
如果新的点不在范围内,或者这个点没有之前标记过(就是不存在需要融合的情况)
continue
找到这个新位置的root,如果这个newRoot和当前root不是一个,那么就说明需要融合
roots[root] = newRoot;
cnt--;
root = newRoot.//这句不可以少,因为如果一个新加的点让cnt+1,但是它成功地连起来了多个点,就会出现多减了的情况,所以要更新root
把cnt加入res中
返回res
代码:
static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<Integer>();
if(m <= 0 || n <= 0 || positions.length == 0 || positions[0].length == 0) {
return res;
}
int[] roots = new int[m * n];
Arrays.fill(roots, -1);
int cnt = 0;
for(int[] point: positions) {
int root = point[0] * n + point[1];
roots[root] = root;
cnt++;
for(int[] dir: dirs) {
int newX = point[0] + dir[0];
int newY = point[1] + dir[1];
int newId = newX * n + newY;
if(newX < 0 || newY < 0 || newX >= m || newY >=n || roots[newId] == -1) {
continue;
}
int newRoot = find(roots, newId);
if(newRoot != root) {
roots[root] = newRoot;
root = newRoot;
cnt--;
}
}
res.add(cnt);
}
return res;
}
private int find(int[] roots, int root) {
if(roots[root] == root) {
return root;
}
return find(roots, roots[root]);
}