题目

给你一个大小为 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^4$
• $1<=m\ast n<=10^4$
• $positions[i].length==2$
• $0<=r_i<m$
• $0<=c_i<n$

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

题解

并查集

【思路】

将二维网格当做无向图，水平或垂直相邻的顶点之间有一条无向边，则问题就是每次 addLand 操作后在图中寻找连通分量的问题。

对于每个 addLand 操作，需要注意的逻辑：

• 如果 addLand 操作的顶点已经访问过，跳过；
• 如果 addLand 操作的顶点没有访问过，此时需要增加连通分量的个数，然后再将它与 「上」「下」「左」「右」合并。

【代码】

class Solution {
private:
    void init(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }

    void merge(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu != pv) {
            parent[pu] = pv;
        }
    }

    vector<int> parent;

public:
    //因为位置是随机的，所以需要一个visited数组保存其相邻的位置是否已经被访问过
    //二维数组转一维
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {

        int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

        init(m * n);

        int cnt = 0;

        vector<int> visited(m * n, false);

        vector<int> ans;    

        for (auto &pos : positions) {
            int x = pos[0], y = pos[1];
            int ind = x * n + y;
            if (!visited[ind]) {
                cnt++; //产生了陆地
                visited[ind] = true;
                for (int i = 0; i < 4; i++) {
                    int xx = x + dir[i][0];
                    int yy = y + dir[i][1];
                    int newInd = xx * n + yy;
                    if (xx < 0 || yy < 0 || xx >= m || yy >= n) continue;
                    if (visited[newInd] && !isConnected(ind, newInd)) { //!!被访问过才是说明是1
                        merge(ind, newInd);
                        cnt--; //合并了陆地，连通分量就减少一个
                    }
                }
            }
            ans.push_back(cnt);
        }

        return ans;
    }
};

【复杂度分析】

• 时间复杂度：$O(klog(mn))$，其中 $k=positions.length$，$m$ 是行数，$n$ 是列数。
• 空间复杂度：$O(m\times n)$，并查集所需的空间。