算法1

这个题与Number of Island I 不同的是，Number of Island 是一个静态的矩阵，可以用BFS DFS 搜索，而这个题是一个stream data，不能一遍又一遍一遍的搜索，而是典型的union find的问题，如果用优化好的union find， 时间复杂度接近于O（k），不会超过O（k log（mn））， 其中k是添加岛屿的操作数，m n 是矩阵长宽

C++ 代码

class UnionFind{
private:
    vector<int> parent;
    vector<int> weight;
    int count;

public:
    UnionFind(int N){
        parent = vector<int> (N, -1);
        weight = vector<int> (N, 0);
        count = 0;
    }

    bool isValid(int i){
        return parent[i] >= 0;
    }

    void SetParent(int i){
        parent[i] = i;
        count++;
    }

    int find(int i){
        if (parent[i]!=i){
            parent[i] = find(parent[i]);
        }

        return parent[i];
    }

    void Union(int x, int y){
        int rootx = find(x);
        int rooty = find(y);

        if (rootx != rooty){
            if (weight[rootx] >= weight[rooty]){
                parent[rooty] = rootx;
                weight[rootx] += weight[rooty];
            }
            else{
                parent[rootx] = rooty;
                weight[rooty] += weight[rootx];
            }
            count--;
        }
    }

    int getCount(){
        return count;
    }

};

class Solution {
public:    
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> result;
        UnionFind uf(m*n);

        for (auto pos : positions){

            int x0 = pos.first;
            int y0 = pos.second;

            int cell0 = x0*n+y0;
            uf.SetParent(cell0);

            vector<int> dx {1, 0, -1, 0};
            vector<int> dy {0, 1, 0, -1};

            for (int i = 0; i < 4; i++){
                int x1 = x0 + dx[i];
                int y1 = y0 + dy[i];

                int cell1 = x1*n + y1;

                if (x1 >=0 && x1 < m && y1 >= 0 && y1 < n && uf.isValid(cell1)){
                    uf.Union(cell1, cell0);
                }   
            }

            result.push_back(uf.getCount());
        }

        return result;       
    }
};