題目資訊

• 題目編號: 1128
• 題目連結: Number of Equivalent Domino Pairs
• 主題: Array, Hash Table, Counting

題目敘述

給定一個 dominoes 列表，若 dominoes[i] = [a, b] 等同於 dominoes[j] = [c, d]，則必須滿足以下條件之一：($a == c$ 且 $b == d$) 或 ($a == d$ 且 $b == c$)。也就是說，一個多米諾骨牌可以旋轉成與另一個多米諾骨牌相等。

返回對數 $(i, j)$，滿足 $0 \leq i < j < dominoes.length$，且 dominoes[i] 與 dominoes[j] 等同。

範例 1：

輸入: dominoes = [[1,2],[2,1],[3,4],[5,6]]
輸出: 1

範例 2：

輸入: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
輸出: 3

限制條件：

• $1 \leq dominoes.length \leq 4 \times 10^{4}$
• $dominoes[i].length == 2$
• $1 \leq dominoes[i][j] \leq 9$

直覺

此問題要求找出等價的多米諾骨牌對，即這些對要麼相同，要麼可以通過交換值來成為等價的。挑戰在於由於多米諾骨牌數量可能非常大，我們需要一種有效的方法來計算這些等價對的數量。我的第一個想法是，我們需要一種快速的方式來判斷兩個多米諾骨牌是否等價，因為直接比較對於較大的輸入而言太慢。

解法

解決此問題的關鍵觀察是，每個多米諾骨牌都可以被唯一地表示，而不考慮其方向性。對於多米諾骨牌 [a, b]，其中 $a \leq b$，我們可以將其轉化為一個單一的整數值。這種轉換的思路是為每種可能的多米諾配置創建一個唯一的哈希值，將多米諾 [a, b] 視為等價於 [b, a]。

1. 唯一表示: 對於每個表示為 [a, b] 的多米諾骨牌，其唯一的哈希值可以通過確保 $a \leq b$ 來計算。當 $a < b$ 時，我們可以計算為 currentVal = a * 9 + b，當 $a > b$ 時，則為 currentVal = b * 9 + a。這為任何 [a, b] 和 [b, a] 提供了一種一致的哈希類型。

2. 使用頻率計數器: 我們利用一個大小為 91 的向量 appearance （因為 $1 \leq a, b \leq 9$）作為計算出的 currentVal 的頻率計數器。這是因為當兩個值都是9時，會發生最大的哈希值，即 $9 \times 9 + 9 = 90$。

3. 計算等價對: 當我們遍歷多米諾骨牌列表時，對於每個多米諾骨牌：

   • 計算其唯一的哈希值 currentVal。
   • 現有的具有相同哈希 currentVal 的多米諾數量直接貢獻於可以形成的對數，其中當前多米諾是所有這樣的對中的一部分。
   • 因此，我們將 appearance 中現有的 currentVal 的數量添加到我們總的等價對數量 count 中，並更新此哈希的 appearance。

4. 返回總數: 處理完所有多米諾骨牌後，累積的 count 變量將包含總的等價多米諾對數。

這種方法確保每個多米諾骨牌的處理時間為常數，導致總體時間複雜度為 $O(n)$，其中 $n$ 是多米諾骨牌的數量。這在給定的約束下是有效的，並確保我們能夠快速處理即使是輸入大小的上限。

程式碼

C++

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int count = 0;
        int currentVal;
        vector<int> appearance(91, 0); // 用來儲存每種獨特骨牌配置的計數

        for (vector<int>& domino : dominoes) {
            // 計算骨牌的一個獨特值，不考慮其方向
            currentVal = (domino[0] < domino[1]) ? domino[0] * 9 + domino[1] : domino[1] * 9 + domino[0];
            
            // 增加目前找到的等效骨牌配對數量
            count += appearance[currentVal]++;
        }

        return count; // 返回總共等效配對的數量
    }
};

Python

class Solution:
    def numEquivDominoPairs(self, dominoes):
        count = 0
        currentVal = 0
        appearance = [0] * 91  # 用於儲存每種獨特多米諾排列的計數

        for domino in dominoes:
            # 計算一個獨特的多米諾值，不考慮其方向
            currentVal = (domino[0] * 9 + domino[1]) if (domino[0] < domino[1]) else (domino[1] * 9 + domino[0])
            
            # 增加到目前為止發現的等價多米諾對的計數
            count += appearance[currentVal]
            appearance[currentVal] += 1

        return count  # 返回等價對的總數量

複雜度分析

• 時間複雜度: $O(n)$

  時間複雜度為 $O(n)$，因為該算法恰好對多米諾骨牌列表進行一次迭代。對於每個多米諾，算法執行了一個恆定時間的操作來計算一個唯一的值，這與多米諾的方向無關，並且更新 appearance 向量中的對應計數。假設 $n$ 為多米諾的數量，這導致了相對於輸入列表大小的線性時間複雜度。

• 空間複雜度: $O(1)$

  空間複雜度為 $O(1)$，因為 appearance 向量用於存儲最多 91 種唯一的多米諾配置的計數（$1 \leq a, b \leq 9$ 導致 $\frac{9 \times 10}{2} = 45$ 種唯一的無序對，每個對因為雙向等價性被存儲一次和兩次）。該向量的大小不依賴於輸入大小 $n$，因此在空間上被視為恆定。