🗿字典應用: Most Stones Removed with Same Row or Column_LC#947

Daria Nepriakhina 🇺🇦 on Unsplash

題目敘述 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

[1] Most Stones Removed with Same Row or Column