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

标签: 深度优先搜索 并查集 图 哈希表

难度: Medium

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
  • 不会有两块石头放在同一个坐标点上

Submission

运行时间: 33 ms

内存: 16.6 MB

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n=len(stones)
        p=list(range(n+1))
        def find(i):
            if i!=p[i]:
                p[i]=find(p[i])
            return p[i]
        def union(x,y):
            p[find(x)]=find(y)
        row=defaultdict(int)
        col=defaultdict(int)
        for i,(r,c) in enumerate(stones,1):
            if not row[r]:
                row[r]=i
            else:
                union(i,row[r])
            if not col[c]:
                col[c]=i
            else:
                union(i,col[c])
        return n-sum(i==find(i) for i in range(1,n+1))

Explain

这道题目可以通过并查集的数据结构来解决。每块石头可以通过其行和列来进行连接，如果两块石头处于同一行或同一列，它们可以属于同一个连通分量。并查集可以帮助我们维护这些连通分量的信息。具体步骤如下：1. 初始化并查集。2. 遍历每块石头，将其行和列视为连接点，如果当前行或列已经有石头，就将当前石头与之前的石头进行合并。3. 最后，连通分量的数量即为不能被移除的石头数量，其余的石头都可以被移除。

时间复杂度: O(n \alpha(n))

空间复杂度: O(n)

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n=len(stones)
        p=list(range(n+1))
        def find(i):
            if i!=p[i]:
                p[i]=find(p[i])
            return p[i]
        def union(x,y):
            p[find(x)]=find(y)
        row=defaultdict(int)
        col=defaultdict(int)
        for i,(r,c) in enumerate(stones,1):
            if not row[r]:
                row[r]=i
            else:
                union(i,row[r])
            if not col[c]:
                col[c]=i
            else:
                union(i,col[c])
        return n-sum(i==find(i) for i in range(1,n+1))

Explore

在这个问题中，我们的目标是找出最大数量的石头，这些石头处于同一行或同一列。因此，将行和列作为连接点，可以更直观地表示石头之间的连接关系（即处于同一行或列的石头属于同一个连通分量）。如果我们直接使用石头的索引，就无法直接表达行和列之间的这种关系，处理起来也更加复杂。通过将行和列作为连接点，我们可以轻松地将处于同一行或列的石头归为一组，从而便于使用并查集算法处理。

在提供的代码中，p的长度设置为n+1是为了方便从1开始索引，避免对0的特殊处理。在Python中，列表索引通常从0开始，但在算法中从1开始索引可以使代码更简洁，特别是当涉及到数学或逻辑关系的转化时。此外，这样做能保证索引不会越界，而且更符合某些编程场景的传统习惯。

在遍历stones时从索引1开始是为了匹配并查集中使用的从1开始的索引系统。这样做主要是为了代码的一致性和简洁性，避免在并查集操作中出现将0作为有效节点的混淆。在并查集的实现中，通常预期所有的索引都是有效的，从1开始可以确保0不会被误用，因为在某些场合0可能被作为特殊值或哨兵值。

在这个算法中，每个连通分量代表了至少一行或一列中的所有石头。题目的要求是可以移除除了一个之外的所有同行或同列的石头。因此，每个连通分量至少需要保留一个石头作为代表，以确保行或列的存在。通过统计并查集中根节点的数量（也就是连通分量的数量），我们可以确定至少需要保留的石头数量。每个连通分量中的其他石头都可以被移除，因为它们与至少一个其他石头共行或共列。