0947. 移除最多的同行或同列石头【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 并查集

1. 📝 题目描述

• leetcode

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

2. 🎯 s.1 - 并查集

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[][]} stones
 * @return {number}
 */
var removeStones = function (stones) {
  const parent = new Map()

  const find = (x) => {
    if (!parent.has(x)) parent.set(x, x)
    if (parent.get(x) !== x) parent.set(x, find(parent.get(x)))
    return parent.get(x)
  }

  const union = (x, y) => {
    parent.set(find(x), find(y))
  }

  for (const [r, c] of stones) {
    union(r, c + 10001) // 偏移列号避免与行号冲突
  }

  const roots = new Set()
  for (const [r] of stones) roots.add(find(r))

  return stones.length - roots.size
}

• 时间复杂度：$O(n\times \alpha (n))$，其中 n 是石头数量，$\alpha$ 是反阿克曼函数
• 空间复杂度：$O(n+C)$，C 是坐标范围

算法思路：

• 将每块石头的行号和列号（偏移后）进行 union 操作，表示它们属于同一连通分量
• 最终可移除的石头数 = 石头总数 - 连通分量数（每个连通分量保留一块）