947. Most Stones Removed with Same Row or Column

题目

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]
Output: 0

Note:

1. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

题目大意

在二维平面上，我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。现在，move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。我们最多能执行多少次 move 操作？

提示：

• 1 <= stones.length <= 1000
• 0 <= stones[i][j] < 10000

解题思路

• 给出一个数组，数组中的元素是一系列的坐标点。现在可以移除一些坐标点，移除必须满足：移除的这个点，在相同的行或者列上有一个点。问最终可以移除多少个点。移除到最后必然有些点独占一行，那么这些点都不能被移除。
• 这一题的解题思路是并查集。把所有共行或者共列的点都 union() 起来。不同集合之间是不能相互移除的。反证法：如果能移除，代表存在共行或者共列的情况，那么肯定是同一个集合了，这样就不满足不同集合了。最终剩下的点就是集合的个数，每个集合只会留下一个点。所以移除的点就是点的总数减去集合的个数 len(stones) - uf.totalCount()。
• 如果暴力合并集合，时间复杂度也非常差，可以由优化的地方。再遍历所有点的过程中，可以把遍历过的行和列存起来。这里可以用 map 来记录，key 为行号，value 为上一次遍历过的点的序号。同样，列也可以用 map 存起来，key 为列号，value 为上一次遍历过的点的序号。经过这样的优化以后，时间复杂度会提高不少。

代码

package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

func removeStones(stones [][]int) int {
	if len(stones) <= 1 {
		return 0
	}
	uf, rowMap, colMap := template.UnionFind{}, map[int]int{}, map[int]int{}
	uf.Init(len(stones))
	for i := 0; i < len(stones); i++ {
		if _, ok := rowMap[stones[i][0]]; ok {
			uf.Union(rowMap[stones[i][0]], i)
		} else {
			rowMap[stones[i][0]] = i
		}
		if _, ok := colMap[stones[i][1]]; ok {
			uf.Union(colMap[stones[i][1]], i)
		} else {
			colMap[stones[i][1]] = i
		}
	}
	return len(stones) - uf.TotalCount()
}