描述:二维平面中有 n 块石头,每块石头都在整数坐标点上,且每个坐标点上最多只能有一块石头。如果一块石头的同行或者同列上有其他石头存在,那么就可以移除这块石头。
要求:返回可以移除的石子的最大数量。
不会有两块石头放在同一个坐标点上。
解释:一种移除 5 块石头的方法如下所示:
题目“求最多可以移走的石头数目”也可以换一种思路:“求最少留下的石头数目”。
如果两个石头 A、B 处于同一行或者同一列,我们就可以删除石头 A 或 B,最少留下 1 个石头。
如果三个石头 A、B、C,其中 A、B 处于同一行,B、C 处于同一列,则我们可以先删除石头 A,再删除石头 C,最少留下 1 个石头。
如果有 n 个石头,其中每个石头都有一个同行或者同列的石头,则我们可以将 n - 1 个石头都删除,最少留下 1 个石头。
通过上面的分析,我们可以利用并查集,将同行、同列的石头都加入到一个集合中。这样“最少可以留下的石头”就是并查集中集合的个数。
则答案为:最多可以移走的石头数目 = 所有石头个数 - 最少可以留下的石头(并查集的集合个数)。
最后计算集合个数,可以使用 set 集合去重,然后统计数量。
整体步骤如下:
遍历每块石头的横纵坐标:
然后将当前石头的横纵坐标相连接(加入到并查集中)。
建立一个 set 集合,查找每块石头横坐标所在集合对应的并查集编号,将编号加入到 set 集合中。