0305：岛屿数量 II（★★）

Ian

2015-11-01 约 717 字预计阅读 2 分钟次阅读

力扣第 305 题

题目

给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。

可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [r_i, c_i] 是要执行第 i 次操作的位置 (r_i, c_i) 。

返回一个整数数组 answer ，其中 answer[i] 是将单元格 (r_i, c_i) 转换为陆地后，地图中岛屿的数量。

岛屿的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。

示例 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⁴
1 <= m * n <= 10⁴
positions[i].length == 2
0 <= r_i < m
0 <= c_i < n

进阶：你可以设计一个时间复杂度 O(k log(mn)) 的算法解决此问题吗？（其中 k == positions.length）

分析

并查集模板
由于只关心陆地，所以加入陆地时才初始化 f 值和 cc 值

解答

 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


class DSU:
    def __init__(self,n):
        self.f = [-1]*n
        self.sz = [1]*n
        self.cc = 0
    
    def find(self,x):
        if self.f[x]!=x:
            self.f[x] = self.find(self.f[x])
        return self.f[x]
    
    def union(self,x,y):
        f,sz = self.f,self.sz
        fx,fy = self.find(x),self.find(y)
        if fx==fy:
            return False
        if sz[fx]>sz[fy]:
            fx,fy = fy,fx
        f[fx] = fy
        sz[fy] += sz[fx]
        self.cc -= 1
        return True

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        dsu = DSU(m*n)
        res = []
        for i,j in positions:
            u = i*n+j
            if dsu.f[u]==-1:
                dsu.f[u] = u
                dsu.cc += 1
            for x,y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0<=x<m and 0<=y<n and dsu.f[x*n+y]!=-1:
                    dsu.union(u,x*n+y)
            res.append(dsu.cc)
        return res

66 ms

目录

0305：岛屿数量 II（★★）

题目

分析

解答