2001-可互换矩形的组数

用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。

如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。更规范的说法是，两个矩形满足
widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。

计算并返回 rectangles 中有多少对 可互换 矩形。

示例 1：

**输入：** rectangles = [[4,8],[3,6],[10,20],[15,30]]
**输出：** 6
**解释：** 下面按下标（从 0 开始）列出可互换矩形的配对情况：
- 矩形 0 和矩形 1 ：4/8 == 3/6
- 矩形 0 和矩形 2 ：4/8 == 10/20
- 矩形 0 和矩形 3 ：4/8 == 15/30
- 矩形 1 和矩形 2 ：3/6 == 10/20
- 矩形 1 和矩形 3 ：3/6 == 15/30
- 矩形 2 和矩形 3 ：10/20 == 15/30

示例 2：

**输入：** rectangles = [[4,5],[7,8]]
**输出：** 0
**解释：** 不存在成对的可互换矩形。

提示：

n == rectangles.length
1 <= n <= 105
rectangles[i].length == 2
1 <= widthi, heighti <= 105

解题思路

宽高比，我们可以直接算出来。但是直接用内建的高精度小数的话，很可能会被卡精度。

所以我们把宽高比化成有理数，即宽和高都除以他们的最大公约数。然后用一个hashmap去算同样宽高比的矩形的数量，再之后就转化成一个组合问题啦。
即宽高比相同的矩形有N个，那么他们组成多少个可互换对呢？🤔

很显然，答案是 N*(N-1)/2

代码

class Solution {
public:
    int gcd(int a, int b) {
        if (a < b) return gcd(b, a);
        if (a % b == 0) return b;
        return gcd(b, a%b);
    }
    
    unordered_map<int, unordered_map<int, long long>> cnt;
    
    long long interchangeableRectangles(vector<vector<int>>& rectangles) {
        for (auto r : rectangles) {
            int c = gcd(r[0], r[1]);
            r[0] /= c;
            r[1] /= c;
            
            cnt[r[0]][r[1]]++;
        }
        
        long long ans = 0;
        
        for (auto iter = cnt.begin(); iter != cnt.end(); iter++) {
            for (auto i = iter->second.begin(); i != iter->second.end(); i++) {
                ans += i->second * (i->second - 1) / 2;
            }
        }
        
        
        return ans;
    }
};

相似题目： hash + 计数

|题目|难度|
|———-|————|———-|
|447.回旋镖的数量 |中等|
|2001.可互换矩形的组数 |中等|

关于我

18年毕业于上海交通大学，一个在阿里、字节、腾讯都工作过的工程师，有丰富的面试经验，业余时间也是【悖论13】剧本杀的老板。实在卷不动了，目前(2021.8)在emqx从事存储研发，希望在今年多多输出。
想了解我和我的公司或者一起刷题的可以 +v ： constant_variation

最后，如果对你有帮助，可以点个赞支持一下我哦 也欢迎在leetcode上关注我。