📝 题目描述
题目链接：岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 示例 1：
输入：grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出：1
示例 2：
输入：grid = [
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出：3
|
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '1'
💡 解题思路
方法一：深度优先搜索 & 广度优先搜索
这里以广度优先搜索为例。首先创建一个标记数组，标记哪些岛屿我们访问过。
然后遍历整个二维数组，如果 char 为 1 且标记数组中未访问，则对其进行广度优先搜索，同时答案数量 + 1。
这里注意，入队时就要标记已访问，不然会导致重复入队问题（如果出队时再标记已访问，那么当下次出队其他坐标时，可能会重复遍历到相同的坐标）。
★方法二：并查集
我们可以使用并查集代替搜索。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。
🔧 代码实现
1、深度优先搜索 & 广度优先搜索
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
| class Solution {
public:
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j) {
queue<pair<int, int>> qu;
qu.push({i, j});
visited[i][j] = true;
while(!qu.empty()) {
auto [i, j] = qu.front(); qu.pop();
if ((i + 1) < grid.size() && grid[i + 1][j] == '1' && !visited[i + 1][j]) {
qu.push({i + 1, j});
visited[i + 1][j] = true;
}
if ((j + 1) < grid[0].size() && grid[i][j + 1] == '1' && !visited[i][j + 1]) {
qu.push({i, j + 1});
visited[i][j + 1] = true;
}
if (i - 1 >= 0 && grid[i - 1][j] == '1' && !visited[i - 1][j]) {
qu.push({i - 1, j});
visited[i - 1][j] = true;
}
if (j - 1 >= 0 && grid[i][j - 1] == '1' && !visited[i][j - 1]) {
qu.push({i, j - 1});
visited[i][j - 1] = true;
}
}
}
int numIslands(vector<vector<char>>& grid) {
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
int ans = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
bfs(grid, visited, i, j);
ans++;
}
}
}
return ans;
}
};
|
2、并查集
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
| class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
count = 0;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent.push_back(i * n + j);
++count;
}
else {
parent.push_back(-1);
}
rank.push_back(0);
}
}
}
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unite(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] < rank[rooty]) {
swap(rootx, rooty);
}
parent[rooty] = rootx;
if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
--count;
}
}
int getCount() const {
return count;
}
private:
vector<int> parent;
vector<int> rank;
int count;
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
UnionFind uf(grid);
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);
if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);
if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);
}
}
}
return uf.getCount();
}
};
|
📊 复杂度分析
1、深度优先搜索 & 广度优先搜索
- 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
- 空间复杂度：O(MN)，使用了标记数组；如果使用沉没策略，深度优先搜索为O(MN)，广度优先搜索为O(min(M,N))。
2、并查集
- 时间复杂度：O(MN×α(MN))，其中 M 和 N 分别为行数和列数。注意当使用路径压缩（见
find 函数）和按秩合并（见数组 rank）实现并查集时，单次操作的时间复杂度为 α(MN)，其中 α(x) 为反阿克曼函数，当自变量 x 的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 α(x) 的值不会超过 5，因此也可以看成是常数时间复杂度。
- 空间复杂度：
🎯 总结
