305. 岛屿数量 II 

难度困难130

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

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

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

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

示例 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 <= 104
• 1 <= m * n <= 104
• positions[i].length == 2
• 0 <= ri < m
• 0 <= ci < n

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-islands-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果：

成功，饶了点弯路最终想到并查集。开始想用贪心，但是有围绕一圈再填中间的情况，这种情况无法判断外圈到底几个岛

写的比较啰嗦，没有用连通分量

1. 如果已经填过的直接返回岛屿数目

2. 检查上下左右共几个岛=A

3. 假设上下左右有岛屿，建立并查集链接

4. 算加入后上下左右中共有几个岛=B

5. 岛屿数=所有岛-A+B

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[][] items = new int[m][n];
        List<Integer> ans = new ArrayList<>();
        Union u = new Union(m*n,n);
        int[] directions = new int[]{0,-1,0,1,0};
        int island = 0;
        for(int[] position:positions){
            int x = position[0];
            int y = position[1];
            if(items[x][y]==1) {
                 ans.add(island);
                 continue;
            }
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();

            for(int i = 0; i < 4; i++){
                int x1 = x+directions[i];
                int y1 = y+directions[i+1];
                if(x1>=0&&y1>=0&&x1<m&&y1<n&&items[x1][y1]==1){
                   set1.add(u.root(x1,y1));
                }
            }

            for(int i = 0; i < 4; i++){
                int x1 = x+directions[i];
                int y1 = y+directions[i+1];
                if(x1>=0&&y1>=0&&x1<m&&y1<n&&items[x1][y1]==1){
                   u.connect(x,y,x1,y1);
                }
            }
            for(int i = 0; i < 4; i++){
                int x1 = x+directions[i];
                int y1 = y+directions[i+1];
                if(x1>=0&&y1>=0&&x1<m&&y1<n&&items[x1][y1]==1){
                    set2.add(u.root(x1,y1));
                }
            }
            set2.add(u.root(x,y));
            items[x][y] = 1;
            island = island-set1.size()+set2.size();
            ans.add(island);

            

        }
        return ans;
    }

    class Union{
        int[] parents;
        int[] sizes;
        int size;
        int col;
        public Union(int size,int col){
            this.size = size;
            parents = new int[size];
            sizes = new int[size];
            Arrays.fill(sizes,1);
            for(int i = 0; i < size; i++){
                parents[i] = i;
            }
            this.col = col;
        }

        public void connect(int x1, int y1, int x2, int y2){
            int v1 = x1*col+y1;
            int v2 = x2*col+y2;
            int rootA = root(v1);
            int rootB = root(v2);
            if(rootA == rootB) return;
            if(sizes[rootA]>=sizes[rootB]){
                sizes[rootA]+=sizes[rootB];
                parents[rootB] = rootA;
            }else{
                sizes[rootB]+=sizes[rootA];
                parents[rootA] = rootB;
            }
        }

        public int root(int x, int y){
            int v = x*col+y;
            while (parents[v]!=v){
                parents[v] = root(parents[v]);
                v = parents[v];
            }
            return v;
        }


        public int root(int v){
            while (parents[v]!=v){
                parents[v] = root(parents[v]);
                v = parents[v];
            }
            return v;
        }

    }
}

相关内容：选择 《Java核心技术 卷1》查找相关笔记

评论🌹点赞👍收藏✨关注👀，是送给作者最好的礼物，愿我们共同学习，一起进步

如果对作者发布的内容感兴趣，可点击下方关注公众号 钰娘娘知识汇总 查看更多作者文章哦！