Formatted question description: https://leetcode.ca/all/1128.html
1128. Number of Equivalent Domino Pairs (Easy)
Given a list of dominoes
, dominoes[i] = [a, b]
is equivalent to dominoes[j] = [c, d]
if and only if either (a==c
and b==d
), or (a==d
and b==c
) - that is, one domino can be rotated to be equal to another domino.
Return the number of pairs (i, j)
for which 0 <= i < j < dominoes.length
, and dominoes[i]
is equivalent to dominoes[j]
.
Example 1:
Input: dominoes = [[1,2],[2,1],[3,4],[5,6]] Output: 1
Constraints:
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
Related Topics:
Array
Solution 1.
// OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& A) {
map<vector<int>, int> m;
int ans = 0;
for (auto &v : A) {
sort(begin(v), end(v));
ans += m[v];
m[v]++;
}
return ans;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& A) {
for (auto &v : A) sort(begin(v), end(v));
sort(begin(A), end(A));
int ans = 0;
for (int i = 0, N = A.size(); i < N;) {
int start = i;
while (i < N && A[i] == A[start]) ++i;
int len = i - start;
ans += (len - 1) * len / 2;
}
return ans;
}
};
Solution 3.
// OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& A) {
int cnt[10][10] = {}, ans = 0;
for (auto &v : A) {
if (v[0] > v[1]) swap(v[0], v[1]);
ans += cnt[v[0]][v[1]]++;
}
return ans;
}
};
Java
-
class Solution { public int numEquivDominoPairs(int[][] dominoes) { int length = dominoes.length; for (int i = 0; i < length; i++) { int[] domino = dominoes[i]; if (domino[0] > domino[1]) { int temp = domino[0]; dominoes[i][0] = dominoes[i][1]; dominoes[i][1] = temp; } } Arrays.sort(dominoes, new Comparator<int[]>() { public int compare(int[] array1, int[] array2) { if (array1[0] != array2[0]) return array1[0] - array2[0]; else return array1[1] - array2[1]; } }); int equivalentCount = 0; int consecutive = 1; for (int i = 1; i < length; i++) { int[] prevDomino = dominoes[i - 1]; int[] curDomino = dominoes[i]; if (prevDomino[0] == curDomino[0] && prevDomino[1] == curDomino[1]) consecutive++; else { equivalentCount += consecutive * (consecutive - 1) / 2; consecutive = 1; } } if (consecutive > 1) equivalentCount += consecutive * (consecutive - 1) / 2; return equivalentCount; } }
-
// OJ: https://leetcode.com/problems/number-of-equivalent-domino-pairs/ // Time: O(NlogN) // Space: O(N) class Solution { public: int numEquivDominoPairs(vector<vector<int>>& A) { map<vector<int>, int> m; int ans = 0; for (auto &v : A) { sort(begin(v), end(v)); ans += m[v]; m[v]++; } return ans; } };
-
class Solution(object): def numEquivDominoPairs(self, dominoes): count = dict() for domi in dominoes: hash_ = domi[0] * 10 + domi[1] if domi[0] < domi[1] else domi[1] * 10 + domi[0] if hash_ in count: count[hash_] += 1 else: count[hash_] = 1 res = 0 for v in count.values(): res += v * (v - 1) / 2 return res