How to Compute the Number of Equivalent Domino Pairs?
- 时间:2020-09-23 15:11:59
- 分类:网络文摘
- 阅读:96 次
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: 1Constraints:
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
Bruteforce Algorithm in O(N^2) pairs
The intuitive solution is to bruteforce the O(N^2) pairs and count if they are Equivalent domino pairs.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: int numEquivDominoPairs(vector<vector<int>>& dominoes) { int res = 0; for (int i = 0; i < dominoes.size(); ++ i) { for (int j = i + 1; j< dominoes.size(); ++ j) { if (((dominoes[i][0] == dominoes[j][0]) && (dominoes[i][1] == dominoes[j][1])) || ((dominoes[i][0] == dominoes[j][1]) && (dominoes[i][1] == dominoes[j][0]))) { res ++; } } } return res; } }; |
class Solution { public: int numEquivDominoPairs(vector<vector<int>>& dominoes) { int res = 0; for (int i = 0; i < dominoes.size(); ++ i) { for (int j = i + 1; j< dominoes.size(); ++ j) { if (((dominoes[i][0] == dominoes[j][0]) && (dominoes[i][1] == dominoes[j][1])) || ((dominoes[i][0] == dominoes[j][1]) && (dominoes[i][1] == dominoes[j][0]))) { res ++; } } } return res; } };
The constant space is required and the performance of such algorithm is slow when the size of the input is significant.
O(N) counting using Hash map
The Equivalent pairs can be simplified by sorting the pairs. After re-arrangement of the pair values, we can count them in hash map. And another O(N) is to sum the total combinations. If there are n items for a domino pair, then there are n*(n-1)/2 equivalent domino pairs.
The following C++ uses the STL::minmax_element to return the min and max of the pair values. And the unordered_map (hash map) to do the counting.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: int numEquivDominoPairs(vector<vector<int>>& dominoes) { unordered_map<int, int> data; for (const auto &n: dominoes) { const auto [minv, maxv] = minmax_element(begin(n), end(n)); int key = *minv * 10 + *maxv; data[key] ++; } int res = 0; for (auto it = data.begin(); it != data.end(); ++ it) { auto key = it->first; res += data[key] * (data[key] - 1) / 2; } return res; } }; |
class Solution { public: int numEquivDominoPairs(vector<vector<int>>& dominoes) { unordered_map<int, int> data; for (const auto &n: dominoes) { const auto [minv, maxv] = minmax_element(begin(n), end(n)); int key = *minv * 10 + *maxv; data[key] ++; } int res = 0; for (auto it = data.begin(); it != data.end(); ++ it) { auto key = it->first; res += data[key] * (data[key] - 1) / 2; } return res; } };
A Linear space O(N) is required to store the counters for each domino pair.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:大自然的风光作文400字 泥土 六一欢乐游园作文 永州韦使君新堂记原文及翻译 捕蛇者说原文及翻译 报孙会宗书原文及翻译 尚德缓刑书原文及翻译 上书谏猎原文及翻译 狱中上梁王书原文及翻译 论贵粟疏原文及翻译
- 评论列表
-
- 添加评论