Medium

题目描述

给你 n 个矩形，用一个下标从 0 开始的二维整数数组 rectangles 表示，其中 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 <= 10^5
  • rectangles[i].length == 2
  • 1 <= widthi, heighti <= 10^5

解题思路

这道题的核心思路是利用哈希表统计具有相同宽高比的矩形数量，然后计算组合数。

思路分析：

首先，我们需要理解什么是"可互换"矩形：两个矩形可互换当且仅当它们的宽高比相等。为了避免浮点数精度问题，我们可以将宽高比化简为最简分数形式，即通过最大公约数(GCD)将 width/height 化简为 (width/gcd, height/gcd) 的形式。

算法步骤：

  1. 遍历所有矩形，对每个矩形计算其宽高的最大公约数
  2. 将宽高比化简为最简分数形式 (width/gcd, height/gcd)
  3. 使用哈希表统计每种宽高比出现的次数
  4. 对于每种宽高比，如果有 count 个矩形具有相同的宽高比，那么可以形成的矩形对数为 count * (count-1) / 2

这种方法避免了浮点数运算的精度问题，确保了结果的准确性。时间复杂度为 O(n)，其中 n 是矩形的数量。

代码实现

class Solution {
public:
    long long interchangeableRectangles(vector<vector<int>>& rectangles) {
        unordered_map<string, int> ratioCount;
        
        for (auto& rect : rectangles) {
            int w = rect[0], h = rect[1];
            int g = __gcd(w, h);
            w /= g;
            h /= g;
            string ratio = to_string(w) + "/" + to_string(h);
            ratioCount[ratio]++;
        }
        
        long long result = 0;
        for (auto& p : ratioCount) {
            long long count = p.second;
            result += count * (count - 1) / 2;
        }
        
        return result;
    }
};

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        from math import gcd
        from collections import defaultdict
        
        ratio_count = defaultdict(int)
        
        for w, h in rectangles:
            g = gcd(w, h)
            w, h = w // g, h // g
            ratio_count[(w, h)] += 1
        
        result = 0
        for count in ratio_count.values():
            result += count * (count - 1) // 2
        
        return result

public class Solution {
    public long InterchangeableRectangles(int[][] rectangles) {
        Dictionary<string, int> ratioCount = new Dictionary<string, int>();
        
        foreach (var rect in rectangles) {
            int w = rect[0], h = rect[1];
            int g = GCD(w, h);
            w /= g;
            h /= g;
            string ratio = $"{w}/{h}";
            ratioCount[ratio] = ratioCount.GetValueOrDefault(ratio, 0) + 1;
        }
        
        long result = 0;
        foreach (var count in ratioCount.Values) {
            result += (long)count * (count - 1) / 2;
        }
        
        return result;
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var interchangeableRectangles = function(rectangles) {
    const ratioCount = new Map();
    
    const gcd = (a, b) => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    
    for (const [w, h] of rectangles) {
        const g = gcd(w, h);
        const simplifiedW = w / g;
        const simplifiedH = h / g;
        const ratio = `${simplifiedW}/${simplifiedH}`;
        ratioCount.set(ratio, (ratioCount.get(ratio) || 0) + 1);
    }
    
    let result = 0;
    for (const count of ratioCount.values()) {
        result += count * (count - 1) / 2;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历所有矩形一次，GCD计算为常数时间
空间复杂度O(n)哈希表存储不同的宽高比，最坏情况下所有矩形宽高比都不同

相关题目