947. 移除最多的同行或同列石頭

思路

如果有兩顆石頭同行，可以刪掉其中一個，同列同理。
用並查集將行列有所重複的石頭合併到一起，假如集合大小為 $k$ ，那麼可以刪掉 $k-1$ 的石頭。
如果現在集合是 $\{1,2,3,4,6\},\{5\},\{9,8,7\}$ ，第一個集合刪掉四顆石頭，第二個零顆，第三個兩顆。
集合大小總和是石頭的數量 $n$ ，因此最後答案就是 $n$ 減去集合個數。

• 對於一顆石頭來說，它同時屬於兩個集合，一個代表列，一個代表行。
• 假如新加的石頭並不是某行或某列出現的第一個石頭，就把新石頭合併到第一個石頭所屬的集合

程式碼

並查集

class Solution {
private:
    static const int MX = 1001;
    unordered_map<int, int> rowFirst, colFirst; // 紀錄每行每列第一個出現的石頭編號
    int parent[MX];
    int setCnt;
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY) {
            parent[rootX] = rootY;
            setCnt--;
        }
    }
    void build(int n) {
        rowFirst.clear();
        colFirst.clear();
        iota(parent, parent + n, 0); // stones[i] 石頭所屬的集合，一開始都是下標
        setCnt = n;
    }
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        build(n);
        for(int i = 0; i < n; i++) {
            // 對於一顆石頭來說，它同時屬於兩個集合，一個列，一個行
            int row = stones[i][0];
            int col = stones[i][1];
            if(!rowFirst.contains(row)) {
                // 這一個 row 的第一塊石頭對應的編號
                rowFirst[row] = i;
            }
            else {
                // 新加入的石頭，跟第一塊石頭所屬的集合合併
                unite(rowFirst[row], i); 
            }
            if(!colFirst.contains(col)) {
                colFirst[col] = i;
            }
            else {
                unite(colFirst[col], i);
            }
        }
        return n - setCnt;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$