題目敘述 Most Stones Removed with Same Row or Column
給定一個2D平面，好幾顆石頭散布在不同的點座標。
輸入陣列代表每顆石頭所在的(x, y)座標。如果某顆石頭的x座標或者y座標相同的軸線上，還有其他石頭，
則原本那顆石頭可以移除。
請問最多可以移除幾顆石頭?
測試範例
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: One way to remove 5 stones is as follows:
1. Remove stone [2,2] because it shares the same row as [2,1].
2. Remove stone [2,1] because it shares the same column as [0,1].
3. Remove stone [1,2] because it shares the same row as [1,0].
4. Remove stone [1,0] because it shares the same column as [0,0].
5. Remove stone [0,1] because it shares the same row as [0,0].
Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: One way to make 3 moves is as follows:
1. Remove stone [2,2] because it shares the same row as [2,0].
2. Remove stone [2,0] because it shares the same column as [0,0].
3. Remove stone [0,2] because it shares the same row as [0,0].
Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.
Example 3:
Input: stones = [[0,0]]
Output: 0
Explanation: [0,0] is the only stone on the plane, so you cannot remove it.
約束條件
Constraints:
1 <= stones.length <= 1000
石頭總數介於1顆~1000顆。
0 <= xi, yi<= 10^4
x, y 座標介於 0 ~ 一萬
- No two stones are at the same coordinate point.
所有石頭的位置都相異。
觀察:
題目說x座標相同 或者 y座標相同的時候，可以拿走一顆石頭。
那麼，我們可以把x座標相同 或者 y座標相同的石頭都歸類成同一組。
如果這組有k個石頭，那麼可以陸續拿走k-1顆石頭，直到剩下最後一顆為止。
每組都可以依循相同的操作邏輯去拿石頭。
最後，可以推得，最多可拿石頭總數 = 石頭總數 - 分組的數目。
示意圖
以範例二為例:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
演算法 Disjoint Set 石頭分組
正數都拿來記錄石頭的x座標。
負數都拿來記錄石頭的y座標。
如果兩顆石頭的x座標 或 y座標相等，就歸入同一組。
歸入同一組的操作就對應到Disjoint Set的union()。
查詢屬於那一組的操作就對應到Disjoint Set的find()。
最後計算石頭總數 - 分組數，即可得到 可移除石頭的最大數量。
程式碼 Disjoint Set 石頭分組
class Solution:
def removeStones(self, points):
# Didjoint Set, aka Union-Find
root = {}
def find(x):
if x != root[x]:
root[x] = find(root[x])
return root[x]
def union(x, y):
root.setdefault(x, x)
root.setdefault(y, y)
root[find(x)] = find(y)
for x, y in points:
union(x, -y-1)
return len(points) - len({find(x) for x in root})
複雜度分析
時間複雜度: O(n)
掃描每顆石頭，每顆石頭依據座標分組。
空間複雜度: O(n)
最差情況下，每顆石頭的x座標 y座標都相異，這時候UF所需空間為O(n)
Reference
