LeetCode 305. 岛屿数量 II（并查集）
LeetCode 305. 岛屿数量 II（并查集）
Michael阿明
发布于 2020-07-13 14:38:16
发布于 2020-07-13 14:38:16
1. 题目
假设你设计一个游戏，用一个 m 行 n 列的 2D 网格来存储你的游戏地图。
起始的时候，每个格子的地形都被默认标记为「水」。
我们可以通过使用 addLand 进行操作，将位置 (row, col) 的「水」变成「陆地」。
你将会被给定一个列表，来记录所有需要被操作的位置，然后你需要返回计算出来 每次 addLand 操作后岛屿的数量。
注意：一个岛的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。
你可以假设地图网格的四边均被无边无际的「水」所包围。
请仔细阅读下方示例与解析，更加深入了解岛屿的判定。
示例:
输入: m = 3, n = 3,
positions = [[0,0], [0,1], [1,2], [2,1]]
输出: [1,1,2,3]
解析:
起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
0 0 0
0 0 0
0 0 0
操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。
1 0 0
0 0 0 Number of islands = 1
0 0 0
操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。
1 1 0
0 0 0 岛屿的数量为 1
0 0 0
操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。
1 1 0
0 0 1 岛屿的数量为 2
0 0 0
操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。
1 1 0
0 0 1 岛屿的数量为 3
0 1 0
拓展：
你是否能在 O(k log mn) 的时间复杂度程度内完成每次的计算？
（k 表示 positions 的长度）来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-islands-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
参考数据结构：并查集（Disjoint-Set）
2.1 超时解
125 / 162 个通过测试用例
- 将矩阵的每个位置看成并查集中的一个点，每次加入一个岛屿，把四周是1的点合并掉
- 计算集团个数
- 时间复杂度 O(kmn)O(kmn)O(kmn)
class dsu
{
public:
vector<int> f;
dsu(int n)
{
f.resize(n);
for(int i = 0; i < n; ++i)
f[i] = i;
}
void merge(int a, int b)
{
int fa = find(a);
int fb = find(b);
f[fa] = fb;
}
int find(int a)
{
int origin = a;
while(a != f[a])
a = f[a];
return f[origin] = a;
}
int countUni(vector<vector<int>> &grid)
{
int count = 0, x, y, n = grid[0].size();
for(int i = 0; i < f.size(); ++i)
{
x = i/n, y = i-x*n;
if(i == find(i) && grid[x][y]==1)
count++;
}
return count;
}
};
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
int N = m*n, pos, x, y;
vector<vector<int>> grid(m,vector<int>(n,0));
dsu u(N);
vector<int> ans(positions.size());
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
for(int i = 0, k; i < positions.size(); ++i)
{
grid[positions[i][0]][positions[i][1]] = 1;//标记为岛屿
pos = positions[i][0]*n+positions[i][1];//对应并查集中的位置
for(k = 0; k < 4; ++k)
{
x = positions[i][0] + dir[k][0];
y = positions[i][1] + dir[k][1];//周围坐标x,y
if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1)
u.merge(pos, x*n+y);//合并
}
ans[i] = u.countUni(grid);
}
return ans;
}
};2.1 改进计算方法
- 并查集merge 函数返回是否被合并了，合并了数量就减1
- 注意有重复岛屿，不能算
class dsu
{
public:
vector<int> f;
dsu(int n)
{
f.resize(n);
for(int i = 0; i < n; ++i)
f[i] = i;
}
bool merge(int a, int b)
{
int fa = find(a);
int fb = find(b);
if(fa != fb)
{
f[fa] = fb;
return true;
}
return false;//返回是否被合并了
}
int find(int a)
{
int origin = a;
while(a != f[a])
a = f[a];
return f[origin] = a;
}
};
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
int N = m*n, pos, x, y;
vector<vector<int>> grid(m,vector<int>(n,0));
dsu u(N);
vector<int> ans(positions.size());
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
unordered_set<int> s;//有重复的岛屿！！！
for(int i = 0, k; i < positions.size(); ++i)
{
ans[i] = (i>0 ? ans[i-1] : 0 )+1;//先把这个岛屿算作孤立+1
grid[positions[i][0]][positions[i][1]] = 1;//标记为岛屿
pos = positions[i][0]*n+positions[i][1];//对应并查集中的位置
if(s.count(pos))//有该岛屿了，重复添加
{
ans[i]--;
continue;
}
s.insert(pos);
for(k = 0; k < 4; ++k)
{
x = positions[i][0] + dir[k][0];
y = positions[i][1] + dir[k][1];//周围坐标x,y
if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1)
{
if(u.merge(pos, x*n+y))//合并了
ans[i]--;//减1
}
}
}
return ans;
}
};156 ms 34.7 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/07/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
