原文链接: https://leetcode-cn.com/problems/number-of-pairs-of-interchangeable-rectangles

英文原文

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [widthi, heighti] denotes the width and height of the ith rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if widthi/heighti == widthj/heightj (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

 

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.

 

Constraints:

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

中文题目

用一个下标从 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上关注我。

统计信息

通过次数	提交次数	AC比率
6001	16627	36.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言