1128. 等价多米诺骨牌对的数量

🎯 问题描述（来源于LeetCode）

描述：
给你一个多米诺骨牌列表 dominoes，其中 dominoes[i] = [a, b]。
如果两个多米诺骨牌是等价的，即满足以下任一条件：

a == c 且 b == d
a == d 且 b == c

也就是说，骨牌可以旋转 180 度后相等。
请你找出列表中等价多米诺骨牌对的数量 (i, j)，其中 0 <= i < j < dominoes.length。

说明：

这是一个哈希表计数问题。
核心逻辑是将骨牌标准化（例如排序），使得等价的骨牌拥有相同的键。
利用组合数学或累加计数法计算对数。
示例：
示例 1：

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1
解释：
- [1,2] 和 [2,1] 是等价的（旋转后相同）。
- 只有一对等价骨牌。

示例 2：

输入：dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
输出：3
解释：
- [1,2] 出现了 3 次。
- 3 个相同的元素可以组成 C(3,2) = 3 对。

💻 解题思路

思路1：哈希表 + 累加计数

思路1：代码实现

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        count = 0
        # 哈希表：键为标准化后的骨牌元组，值为该骨牌出现的次数
        num = defaultdict(int)
        
        for nums in dominoes:
            # 1. 标准化骨牌：排序后转为元组
            # 这样 [1,2] 和 [2,1] 都会变成 (1,2)
            nums = tuple(sorted(nums))
            
            # 2. 累加计数
            # 如果当前骨牌之前出现过 k 次，那么它可以与之前的 k 个骨牌分别组成一对
            # 所以直接加上 num[nums]
            count += num[nums]
            
            # 3. 更新计数
            num[nums] += 1
            
        return count

思路1：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是 dominoes 的长度。
- 遍历数组一次。
- sorted(nums) 的时间复杂度是 $O(1)$ ，因为骨牌只有两个数字，排序操作是常数时间的。
- 哈希表操作平均为 $O(1)$ 。
- 总时间复杂度为 $O(N)$ 。
空间复杂度： $O(N)$ $O (N)$
- 哈希表 num 在最坏情况下需要存储 $N$ 个键值对。

思考

标准化（归一化）：
- 多米诺骨牌 [a, b] 和 [b, a] 是等价的。
- 为了在哈希表中将它们视为同一个键，我们需要对骨牌进行标准化。
- 代码中使用 tuple(sorted(nums))，将 [2, 1] 变为 (1, 2)，将 [1, 2] 也变为 (1, 2)。这样就统一了键。
累加计数原理：
- 假设某种骨牌已经出现了 $k$ 次。
- 当我们遇到第 $k+1$ 个该种骨牌时，它可以与之前的 $k$ 个骨牌分别组成一对。
- 因此，新增的对数就是 $k$ 。
- 代码中的 count += num[nums] 正是利用了这一点。
- 这等价于最后计算组合数 $C_n^2 = \frac{n(n-1)}{2}$ ，但累加法可以在一次遍历中完成，无需最后再遍历哈希表。
逻辑流程：
- 遍历每个骨牌。
- 将其排序并转为元组，作为哈希表的键。
- 查看该键在哈希表中的当前计数 num[nums]。
- 将 num[nums] 加到 count 中（表示当前骨牌与之前的骨牌组成了多少对）。
- 将 num[nums] 加 1（更新计数）。
边界情况：
- 数组长度为 1：count 加 0，返回 0。
- 所有骨牌都不同：num[nums] 始终为 0，count 始终为 0。
- 所有骨牌都相同：第 $i$ 个骨牌会增加 $i-1$ 个对数，总对数为 $0+1+2+...+(N-1) = \frac{N(N-1)}{2}$ 。