题面
给你一个由 ’1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
题解
我的题解
我们可以将二维网格看成一个无向图，竖直或水平相邻的1之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的1都会被重新标记为2。
最终岛屿的数量就是我们进行深度优先搜索的次数。
class Solution
{
public:
int numIslands(vector<vector<char>>& grid)
{
int num = 0;
for (int i = 0; i < grid.size(); ++i)
{
for (int j = 0; j < grid[i].size(); ++j)
{
if (grid[i][j] == '0' || grid[i][j] == '2')
{
}
else
{
++num;
change(grid, i, j);
}
}
}
return num;
}
void change(vector<vector<char>>& grid, int x, int y)
{
if (grid[x][y] == '1')
{
grid[x][y] = '2';
if (x > 0)
{
change(grid, x - 1, y);
}
if (x+1 < grid.size())
{
change(grid, x + 1, y);
}
if (y > 0)
{
change(grid, x, y - 1);
}
if (y+1 < grid[x].size())
{
change(grid, x, y + 1);
}
}
}
};
复杂度分析
时间复杂度：O(MN)O(MN)，其中 MM 和 NN 分别为行数和列数。
空间复杂度：O(MN)O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 M NMN。
并查集
同样地，我们也可以使用并查集代替搜索。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其与相邻四个方向上的 11 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。
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();
}
};
复杂度分析
时间复杂度：O(MN * \alpha(MN))O(MN∗α(MN))，其中 MM 和 NN 分别为行数和列数。注意当使用路径压缩（见 find 函数）和按秩合并（见数组 rank）实现并查集时，单次操作的时间复杂度为 \alpha(MN)α(MN)，其中 \alpha(x)α(x) 为反阿克曼函数，当自变量x的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 \alpha(x)α(x) 的值不会超过 55，因此也可以看成是常数时间复杂度。
空间复杂度：O(MN)O(MN)，这是并查集需要使用的空间。
Related Issues not found
Please contact @zhaiyunfan to initialize the comment
