2001. 可互换矩形的组数

🎯 问题描述（来源于LeetCode）

描述：
给你一个二维整数数组 rectangles，其中 rectangles[i] = [width_i, height_i] 表示第 i 个矩形的宽度和高度。
如果两个矩形 i 和 j（i < j）的宽高比相同，则认为它们是可互换的。
具体来说，如果 width_i / height_i == width_j / height_j，则这两个矩形可互换。
请你返回可互换矩形的组数。

说明：

这是一个哈希表计数结合组合数学的问题。
核心逻辑是将矩形按照“宽高比”进行分组。
对于同一组内的 $k$ 个矩形，它们可以组成的对数为 $C_k^2 = \frac{k(k-1)}{2}$ 。
代码采用了累加计数法，在遍历过程中直接计算新增的对数。
示例：
示例 1：

输入：rectangles = [[4,8],[3,6],[10,20],[15,30]]
输出：2
解释：
- [4,8] 的宽高比为 0.5。
- [3,6] 的宽高比为 0.5。
- [10,20] 的宽高比为 0.5。
- [15,30] 的宽高比为 0.5。
- 共有 4 个矩形宽高比为 0.5。
- 组数为 C(4,2) = 6。

示例 2：

输入：rectangles = [[4,5],[7,8]]
输出：0
解释：
- 没有可互换的矩形。

💻 解题思路

思路1：哈希表 + 累加计数

思路1：代码实现

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        # 哈希表：键为宽高比，值为该比例出现的次数
        count = defaultdict(int)
        ans = 0
        
        for w, h in rectangles:
            # 计算宽高比
            rate = w / h
            
            # 如果该比例之前出现过
            if rate in count:
                # 当前矩形可以与之前的所有同比例矩形组成一对
                # 假设之前出现了 k 次，那么新增的对数就是 k
                ans += count[rate]
            
            # 更新该比例的出现次数
            count[rate] += 1
            
        return ans

思路1：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是 rectangles 的长度。
- 遍历数组一次，每次哈希表操作平均为 $O(1)$ 。
- 总时间复杂度为 $O(N)$ 。
空间复杂度： $O(N)$ $O (N)$
- 哈希表 count 在最坏情况下需要存储 $N$ 个键值对。

思考

累加计数原理：
- 假设某种宽高比的矩形已经出现了 $k$ 次。
- 当我们遇到第 $k+1$ 个该比例的矩形时，它可以与之前的 $k$ 个矩形分别组成一对。
- 因此，新增的对数就是 $k$ 。
- 代码中的 ans += count[rate] 正是利用了这一点。
- 这等价于最后计算组合数 $C_n^2 = \frac{n(n-1)}{2}$ ，但累加法可以在一次遍历中完成。
浮点数精度问题（重要）：
- 代码中直接使用 w / h 作为键。在 Python 中，浮点数作为字典键通常是可行的，但在某些极端情况下（非常大的整数或精度极高的除法），可能会出现精度误差导致 0.5 和 0.5000000000000001 被视为不同的键。
- 更严谨的做法：使用最简分数作为键。
- 计算 g = gcd(w, h)，然后使用元组 (w // g, h // g) 作为哈希表的键。这样可以完全避免浮点数精度问题。
逻辑流程：
- 遍历每个矩形 [w, h]。
- 计算其宽高比 rate。
- 检查 rate 是否在哈希表中：
  - 存在：说明之前遇到过相同比例的矩形。将当前的计数 count[rate] 加到 ans 中（表示新增了多少对）。
  - 不存在：说明第一次遇到该比例。
- 将 count[rate] 加 1。
边界情况：
- 数组长度为 1：无法组成对，返回 0。
- 所有矩形比例都不同：ans 始终为 0。
- 所有矩形比例都相同：第 $i$ 个矩形会增加 $i-1$ 个对数，总对数为 $\sum_{i=1}^{N-1} i = \frac{N(N-1)}{2}$ 。