可互换矩形的组数

标签: 数组 哈希表 数学 计数 数论

难度: Medium

用一个下标从 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

Submission

运行时间: 144 ms

内存: 61.5 MB

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        return sum([x*(x-1)//2 for x in (Counter([w/h for w,h in rectangles]).values())])

Explain

The solution leverages a hash map (Counter) to record the frequency of each unique width-to-height ratio encountered among the rectangles. Instead of using the raw division result, which could suffer from floating-point precision issues, it implicitly uses the ratio of width to height. For each unique ratio found, if there are 'x' rectangles with that ratio, the number of interchangeable pairs among these rectangles can be calculated using the combination formula 'x choose 2', which simplifies to x*(x-1)/2. This approach counts all such pairs across different unique ratios.

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        # Counter to count rectangles by their width-to-height ratio
        from collections import Counter
        # Compute ratio for each rectangle and store in Counter
        ratio_count = Counter(w/h for w, h in rectangles)
        # Calculate the number of interchangeable pairs using combinations of rectangles with the same ratio
        return sum(x * (x - 1) // 2 for x in ratio_count.values())

Explore

选择使用`w/h`作为矩形宽高比的表示是出于对比例一致性的考虑。使用`w/h`可以直接反映矩形的形状比例，因为在几何学中，这种比例能够唯一确定一个矩形的相似类。如果使用`h/w`，虽然也能达到相似的效果，但需要保持使用一致性以避免混淆。此外，使用两者的差异（如`w-h`）则不能正确反映矩形的比例关系，因为不同的矩形可能有相同的差异但形状比例完全不同。

为了避免浮点数精度问题，实际上应该避免直接使用`w/h`的浮点结果作为键存储。一种常见的方法是使用整数比来表示，即通过存储每个矩形宽高比的最简分数形式。可以通过计算宽度和高度的最大公约数，然后用宽度除以最大公约数和高度除以最大公约数得到约简后的比例。这样，即使宽高比为有理数，其最简分数形式也可以精确表示，从而避免了浮点数的精度问题。

如果直接使用浮点数结果作为键，确实可能因为浮点数的精度问题导致本应相等的比例被认为是不相等的。例如，由于计算误差，两个非常接近的浮点数可能不完全相等。正如之前所述，最佳做法是使用整数比（即最简分数形式），这样可以完全避免这种情况，确保只有真正具有相同宽高比的矩形才会被计算在内。

当你有`x`个相同宽高比的矩形时，你可以从这`x`个矩形中任选两个来形成一对。组合数`C(x, 2)`即是从`x`个元素中选择两个不同元素的方法数，其公式为`x*(x-1)/2`。这是因为每选择一个矩形，都有`x-1`个其他矩形可以与之配对，然后由于每对矩形被计算了两次（一次以A为第一个，B为第二个，一次以B为第一个，A为第二个），所以需要将结果除以2。这种计算方法简单且直接反映了组合的本质。