题目
给你一个大小为 m x n
的二进制网格 grid
。网格表示一个地图,其中,0
表示水,1
表示陆地。最初,grid
中的所有单元格都是水单元格(即,所有单元格都是 0
)。
可以通过执行 addLand
操作,将某个位置的水转换成陆地。给你一个数组 positions
,其中 positions[i] = [ri, ci]
是要执行第 i
次操作的位置 (ri, ci)
。
返回一个整数数组 answer
,其中 answer[i]
是将单元格 (ri, ci)
转换为陆地后,地图中岛屿的数量。
岛屿 的定义是被「水」包围的「陆地」,通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。
示例 1:
输入:m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出:[1,1,2,3]
解释:
起初,二维网格 `grid` 被全部注入「水」。(0 代表「水」,1 代表「陆地」)
- 操作 #1:`addLand(0, 0)` 将 `grid[0][0]` 的水变为陆地。此时存在 1 个岛屿。
- 操作 #2:`addLand(0, 1)` 将 `grid[0][1]` 的水变为陆地。此时存在 1 个岛屿。
- 操作 #3:`addLand(1, 2)` 将 `grid[1][2]` 的水变为陆地。此时存在 2 个岛屿。
- 操作 #4:`addLand(2, 1)` 将 `grid[2][1]` 的水变为陆地。此时存在 3 个岛屿。
示例 2:
输入:m = 1, n = 1, positions = [[0,0]]
输出:[1]
提示:
1 <= m, n, positions.length <= 10^4
1 <= m * n <= 10^4
positions[i].length == 2
0 <= ri < m
0 <= ci < n
进阶:你可以设计一个时间复杂度 O(k log(mn))
的算法解决此问题吗?(其中 k == positions.length
)
解题
方法一:并查集
思路
把二维的网格图当做一个无向图,横向或者纵向相邻的顶点之间有一条无向边,那么问题就变成了每次 addLand
操作之后在图中寻找连通分量的问题。
对于每个 addLand
操作。需要注意的逻辑是:
- 如果
addLand
操作的顶点已经访问过,跳过; - 如果
addLand
操作的顶点没有访问过,此时需要增加连通分量个数,然后再将它与「上」「下」「左」「右」合并。
代码
class Solution {
private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
int size = m * n;
UnionFind uf = new UnionFind(size);
boolean[] visited = new boolean[size];
List<Integer> ans = new ArrayList<>();
for (int[] pos : positions) {
int row = pos[0], col = pos[1];
int idx = row * n + col;
if (!visited[idx]) {
uf.count++; // // 把水变成陆地,连通分量个数加 1
visited[idx] = true;
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
if (newRow < 0 || newRow >= m) continue;
int newCol = col + direction[1];
if (newCol < 0 || newCol >= n) continue;
int newIdx = newRow * n + newCol;
if (visited[newIdx]) uf.union(idx, newIdx);
}
}
ans.add(uf.count);
}
return ans;
}
static class UnionFind {
public int count;
private int[] root;
private int[] rank;
public UnionFind() {}
public UnionFind(int size) {
count = 0;
root = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
root[i] = i;
rank[i] = 1;
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] > rank[rootQ]) {
root[rootQ] = rootP;
} else if (rank[rootP] < rank[rootQ]) {
root[rootP] = rootQ;
} else {
root[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
public int find(int n) {
return n == root[n] ? n : (root[n] = find(root[n]));
}
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
}
评论区