题目描述

给定一个多米诺列表，dominoes[i] = [a, b] 等价于 dominoes[j] = [c, d] 当且仅当 a == c 且 b == d 或者 a == d 且 b == c，即，一个多米诺可以经过旋转等于另一个多米诺。

然后数对 (i, j) 的数量，其中 0 <= i < j < domoines.length，且 dominoes[i] 等价于 dominoes[j]。

样例

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1

限制

• 1 <= dominoes.length <= 40000
• 1 <= dominoes[i][j] <= 9

算法

(哈希表) $O(n)$

1. 如果数对中出现 x > y 的情况，则交换 x 和 y，然后变成字符串类型去哈希表查询出现的次数，累计答案，然后更新哈希表。

时间复杂度

• 仅遍历数组一次，哈希表修改和查询的时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的哈希表空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int n = dominoes.size();
        unordered_map<string, int> visited;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int x = dominoes[i][0], y = dominoes[i][1];
            if (x > y)
                swap(x, y);

            string h(to_string(x) + to_string(y));
            if (visited.find(h) != visited.end()) {
                ans += visited[h];
                visited[h]++;
            } else {
                visited[h] = 1;
            }
        }
        return ans;
    }
};