Question

2001. 可互换矩形的组数

English Version

题目描述

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

解法

方法一：数学 + 哈希表

为了能够唯一表示矩形，我们需要将矩形的宽高比化简为最简分数。因此，我们可以求出每个矩形的宽高比的最大公约数，然后将宽高比化简为最简分数。接下来，我们使用哈希表统计每个最简分数的矩形数量，然后计算每个最简分数的矩形数量的组合数，即可得到答案。

时间复杂度 $O(n \times \log M)$，空间复杂度 $O(n)$。其中 $n$ 和 $M$ 分别是矩形的数量和矩形的最大边长。

class Solution:
  def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
    ans = 0
    cnt = Counter()
    for w, h in rectangles:
      g = gcd(w, h)
      w, h = w // g, h // g
      ans += cnt[(w, h)]
      cnt[(w, h)] += 1
    return ans

class Solution {
  public long interchangeableRectangles(int[][] rectangles) {
    long ans = 0;
    int n = rectangles.length + 1;
    Map<Long, Integer> cnt = new HashMap<>();
    for (var e : rectangles) {
      int w = e[0], h = e[1];
      int g = gcd(w, h);
      w /= g;
      h /= g;
      long x = (long) w * n + h;
      ans += cnt.getOrDefault(x, 0);
      cnt.merge(x, 1, Integer::sum);
    }
    return ans;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

class Solution {
public:
  long long interchangeableRectangles(vector<vector<int>>& rectangles) {
    long long ans = 0;
    int n = rectangles.size();
    unordered_map<long long, int> cnt;
    for (auto& e : rectangles) {
      int w = e[0], h = e[1];
      int g = gcd(w, h);
      w /= g;
      h /= g;
      long long x = 1ll * w * (n + 1) + h;
      ans += cnt[x];
      cnt[x]++;
    }
    return ans;
  }
};

func interchangeableRectangles(rectangles [][]int) int64 {
  ans := 0
  n := len(rectangles)
  cnt := map[int]int{}
  for _, e := range rectangles {
    w, h := e[0], e[1]
    g := gcd(w, h)
    w, h = w/g, h/g
    x := w*(n+1) + h
    ans += cnt[x]
    cnt[x]++
  }
  return int64(ans)
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}

/**
 * @param {number[][]} rectangles
 * @return {number}
 */
var interchangeableRectangles = function (rectangles) {
  const cnt = new Map();
  let ans = 0;
  for (let [w, h] of rectangles) {
    const g = gcd(w, h);
    w = Math.floor(w / g);
    h = Math.floor(h / g);
    const x = w * (rectangles.length + 1) + h;
    ans += cnt.get(x) | 0;
    cnt.set(x, (cnt.get(x) | 0) + 1);
  }
  return ans;
};

function gcd(a, b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}