# 0947. 移除最多的同行或同列石头 ### 题目地址 (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] 是平面上唯一一块石头，所以不可以移除它。   提示： 1 <= stones.length <= 1000 0 <= xi, yi <= 104 不会有两块石头放在同一个坐标点上 ``` ### 前置知识 * [并查集](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/union-find) ### 思路 读完题目之后， 看了下数据范围。我猜测可能和动态规划什么的有关，**而且时间复杂度是 $O(n^2)$ 左右**，其中 n 为 stones 的长度。继续看了下示例，然后跟着思考了一下，发现很像是某种联通关系。 类似的题目有很多，题目描述记不太清楚了。大概意思是给你一个二维网格，行和列需要**一起增加**，求最小和什么的。这类题目都是行和列具有某种绑定关系。 于是我想到了使用并查集来做。 后面想了一下，反正就是**求联通区域的个数**，因此使用 DFS 和 BFS 都可以。如果你想使用 DFS 或者 BFS 来解，可以结合我之前写的 [小岛专题](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/island) 练习一下哦。 继续分析下题目。 题目的意思是任意一个石头可以消除和它同行和同列的其他石子。于是我就想象出了下面这样一幅图，其中红色的方块表示石子，方块的连线表示离得最近的可以消除的石子。实际上，一个石子除了可以消除图中线条直接相连的石子，还可以消除邻居的邻居。**这提示我们使用并查集维护这种联通关系**，联通的依据自然就是列或者行一样。 ![](https://p.ipic.vip/0g23sy.jpg) 上面是一个全联通的图。如下是有两个联通域的图。 ![](https://p.ipic.vip/9ysm39.jpg) 有了上面的知识，其实就可以将石子全部建立并查集的联系，并计算联通子图的个数。答案就是 n - 联通子图的个数，其中 n 为 stones 的长度。 核心代码： ```py n = len(stones) # 标准并查集模板 uf = UF(n) # 两个 for 循环作用是将所有石子两两合并 for i in range(n): for j in range(i + 1, n): # 如果行或者列相同，将其联通成一个子图 if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]: uf.union(i, j) return n - uf.cnt ``` 有的人想问，这可行么？即**我可以将一个联通子图的石子移除只剩下一个么？** 答案是肯定的。其实上面我提到了这道题也可使用 DFS 和 BFS 的方式来做。如果你使用 DFS 的方式来做，会发现其实 **DFS 路径的取反就是消除的顺序**，当然消除的顺序不唯一，因为遍历访问联通子图的序列并不唯一。 如果题目要求我们求移除顺序，那我们可以考虑使用 DFS 来做，同时记录路径信息即可。 ![](https://p.ipic.vip/b62ori.jpg) 使用遍历的方式（BFS 或者 DFS），由于每次访问一个石子都需要使用 visited 来记录访问信息防止环的产生，因此 visited 的逆序也是一个可行的移除顺序。不过这要求你的 visited 的是有序的。实现的方法有很多，有点偏题了，这里就不赘述了。 实际上，上面的并查集代码仍然可以优化。上面的思路是直接将点作为并查集的联通条件。实际上，我们可以将点的横纵坐标分别作为联通条件。即如果横坐标相同的联通到一个子图，纵坐标相同的联通到一个子图。如下图： ![](https://p.ipic.vip/z3q3o8.jpg) 为了达到这个模板，我们不能再初始化的时候计算联通域数量了，即不能像上面那样 `uf = UF(n)`（此时联通域个数为 n）。因为横坐标，纵坐标分别有多少不重复的我们是不知道的，一种思路是先计算出**横坐标，纵坐标分别有多少不重复的**。这当然可以，还有一种思路是在 find 过程中计算，这样 one pass 即可完成，具体见下方代码区。 由于我们需要**区分横纵坐标**（上面图也可以看出来），因此可**用一种映射**区分二者。由于题目限定了横纵坐标取值为 10000 以内（包含 10000），一种思路就是将 x 或者 y 加上 10001。 核心代码： ```py n = len(stones) uf = UF(0) for i in range(n): uf.union(stones[i][0] + 10001, stones[i][1]) return n - uf.cnt ``` ### 代码 #### 并查集 代码支持： Python3 其中 `class UF` 部分是标准的无权并查集模板，我一行代码都没变。关于模板可以去 [并查集](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/union-find) 查看。 ```python class UF: def __init__(self, M): self.parent = {} self.cnt = 0 # 初始化 parent，size 和 cnt for i in range(M): self.parent[i] = i self.cnt += 1 def find(self, x): if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return leader_p = self.find(p) leader_q = self.find(q) self.parent[leader_p] = leader_q self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) class Solution: def removeStones(self, stones: List[List[int]]) -> int: n = len(stones) uf = UF(n) for i in range(n): for j in range(i + 1, n): if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]: uf.union(i, j) return n - uf.cnt ``` **复杂度分析** 令 n 为数组 stones 的长度。 * 时间复杂度：$O(n^2logn)$ * 空间复杂度：$O(n)$ #### 优化的并查集 代码支持： Python3 ```py class UF: def __init__(self, M): self.parent = {} self.cnt = 0 def find(self, x): if x not in self.parent: self.cnt += 1 self.parent[x] = x if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return leader_p = self.find(p) leader_q = self.find(q) self.parent[leader_p] = leader_q self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) class Solution: def removeStones(self, stones: List[List[int]]) -> int: n = len(stones) uf = UF(0) for i in range(n): uf.union(stones[i][0] + 10001, stones[i][1]) return n - uf.cnt ``` **复杂度分析** 令 n 为数组 stones 的长度。 * 时间复杂度：$O(nlogn)$ * 空间复杂度：$O(n)$ #### DFS 代码支持： Java > by 一位不愿透露姓名的热心网友。 ```java public int removeStones(int[][] stones) { Set visit = new HashSet(); int count = 0; int offset = 10000; HashMap >map = new HashMap(); // 构造图 每一项是一个节点 for (int i = 0; i < stones.length; i++) { int [] node = stones[i]; List list = map.getOrDefault(node[0]-offset,new ArrayList<>()); list.add(node); map.put(node[0]-offset,list); List list1 = map.getOrDefault(node[1],new ArrayList<>()); list1.add(node); map.put(node[1],list1); } // 寻找联通分量 for (int i = 0; i < stones.length; i++) { int [] node = stones[i]; if (!visit.contains((node))){ visit.add((node)); dfs(node,visit,map); count++; } } return stones.length-count; } // 遍历节点 public void dfs(int[]node, Set set,HashMap >map){ int offset = 10000; List list = map.getOrDefault(node[0]-offset,new ArrayList<>()); for (int i = 0; i < list.size(); i++) { int[] item = list.get(i); if (!set.contains((item))){ set.add((item)); dfs(item,set,map); } } List list2 = map.getOrDefault(node[1],new ArrayList<>()); for (int i = 0; i < list2.size(); i++) { int[] item = list2.get(i); if (!set.contains((item))){ set.add((item)); dfs(item,set,map); } } } ``` **复杂度分析** 令 n 为数组 stones 的长度。 * 时间复杂度：建图和遍历图的时间均为 $O(n)$ * 空间复杂度：$O(n)$ 力扣的小伙伴的点下我头像的关注按钮，这样就会第一时间收到我的动态啦\~ 以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 38K star 啦。