侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【图, 并查集】岛屿数量 II

GabrielxD
2022-06-01 / 0 评论 / 0 点赞 / 454 阅读 / 920 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

305. 岛屿数量 II


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

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

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

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

示例 1:

image-20220726220243320

输入: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);
        }
    }
}
0

评论区