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: 1

Constraints:
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) —

推荐阅读:
若这稿件由乙完成,需要几小时?  从上边剪下一块直径是80厘米的圆片  甲乙丙三个修路队共同修完一条公路  最多可做多少面小三角旗  客车从甲地开往乙地需要10小时  遇店加一半,遇花喝一斗  这些车共有86个轮子  wordpress使用短代码实现在父页面中显示子页面列表链接  使用 wordpress 插件 Backend Designer 自定义后台颜色风格  如何更改 WordPress 默认发件人及邮箱地址 
评论列表
添加评论