题目

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

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

示例 1：

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

示例 3：

输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。

解法一

思路

这一题和普通的并查集不太一样，普通的我们遇到过，基本都是点与点合并成一个连通分量。

这一题，是横纵坐标合并成一个连通分量。

如题[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]，我们将这些点画出来如下

那么，我可以认为这些红色的线将这些点连接成了一个连通分量，那么这样的一个连通分量，总可以一个一个点的去删除，最后只剩下一个点，这个大家可以用纸笔画一下试试。

这里就很关键了，将点连接成连通分量的元素并不是点的绝对坐标，而是横坐标和纵坐标。

我们可以理解为，

(0,0)点，将横坐标线0和纵坐标线0连接在一起

(0,1)点，将横坐标线0和纵坐标线1连接在一起

(2,2)点，将横坐标线2和纵坐标线2连接在一起

这时候，如果有点(2,5),不用思考，肯定在这个连通分量里，因为横坐标线2在这个连通分量里

如果有点(3,3),一定不在，因为横坐标线3和纵坐标线3都不在这个连通分量里

那这样的话，这一题就成了，求连通分量数count

可删除点的个数 == 点的总个数 – 总连通分量数，即 stones.length – count

但是这里还有一个问题，并查集的底层数组是一维的，没办法区别横坐标还是纵坐标，

比如你用0加入一个连通分量，我压根不知道这是横坐标还是纵坐标

由题可知，0 <= xi, yi <= 10^{4，又因为我们只需要知道删除的个数，并不需要知道具体删除的点是谁}

那么我们可以把横坐标+10001，来和纵坐标区分

1. 建立并查集底层数组parent,parent.count = 0,用来记录连通量,这里这样写不想使用全局变量。
2. 遍历stones，将每个点的横纵坐标合并到一个连通分量
3. 返回 stones.length – parent.count 即可

代码如下

/** * @param {number[][]} stones * @return {number} */
var removeStones = function(stones) {
    let parent = [];
    parent.count = 0;
    for (let stone of stones) {
        union(parent,stone[0] + 10001, stone[1]);
    }
    return stones.length - parent.count;
};


function union(parent,p,q){
    let rootP = find(parent,p);
    let rootQ = find(parent,q);
    if (rootP == rootQ) {
        return;
    }
    parent[rootP] = rootQ;
    parent.count--
}

function find(parent,x){
    if (!parent[x] && parent[x] != 0) {
        parent[x] = x;
        // 并查集集中新加入一个条边，连通分量的总数 +1
        parent.count++;
    }
    if (x != parent[x]) {
        parent[x] = find(parent,parent[x]);
    }
    return parent[x];
}

复杂度分析

时间复杂度：O(nlogn),遍历stones为n，并查集的查找平均为α(n),最坏为logn,故为O(nlogn)。

空间复杂度：O(n)