并查集

如果按照floodfill算法操作stream of data，那么时间复杂度会是 O(k * min(nm))
如果用并查集，根据优化find的方法的不同，时间复杂度会是 O(k) ~ O(k * log(nm)) 之间。按秩合并或者按ranked合并 与 路径压缩 同时写 会把操作优化到到O(1), 理论上只写路径压缩时间复杂度是O(log(n)), 但是实际效果可以看成事 O(1). 实际写和理论之间是有区别的

代码1

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        vector<int> res;
        int cnt = 0;
        vector<int> fa(m * n, -1);
        vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        for (auto &pos : positions) {
            int id = n * pos[0] + pos[1]; // 转换坐标
            if (fa[id] != -1) { // 直接用 fa数组初始化为1代替visited数组来标记，
                res.push_back(cnt);
                continue;
            }
            fa[id] = id; // 只初始化过第一次出现的点
            ++cnt;
            for (auto dir : dirs) {
                int x = pos[0] + dir[0], y = pos[1] + dir[1], cur_id = n * x + y;
                //  利用 fa[cur_id] ！= -1 来判断上下左右是否有岛屿
                if (x < 0 || x >= m || y < 0 || y >= n || fa[cur_id] == -1) continue;
                int p = findRoot(fa, cur_id), q = findRoot(fa, id);
                if (p != q) {
                    // 可以优化
                    fa[p] = q;
                    --cnt;
                }
            }
            res.push_back(cnt);
        }
        return res;
    }
    int findRoot(vector<int>& fa, int id) {
        return (id == fa[id]) ? id : findRoot(fa, fa[id]);
    }
};