2001. Number of Pairs of Interchangeable Rectangles

Medium
Description

給定 rectangles 陣列，每個元素 [width, height] 代表一個矩形。若兩個矩形的寬高比相同（w1/h1 == w2/h2），則稱為可互換。回傳可互換矩形的配對數。

Example:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]] Output: 6 （所有矩形的寬高比都是 1:2，C(4,2) = 6）

Intuition#

核心思路：將每個矩形的寬高比用最簡分數表示（除以 GCD），然後用 HashMap 統計相同比例的數量，再計算組合數 C(n,2)。

  • 直接用浮點數比較可能有精度問題，改用最簡分數 (w/gcd, h/gcd) 作為 key
  • 對每組相同比例的 count 個矩形，配對數為 count * (count - 1) / 2
  • 或者邊遍歷邊累加：新加入一個矩形時，它能與之前所有相同比例的矩形配對

Approaches#

1: HashMap + GCD (Two Pass)#

  • 概念: 先統計每個最簡分數的出現次數，再對每組計算 C(n,2)
  • 時間複雜度: O(n log(max(w,h))) - GCD 計算為 O(log)
  • 空間複雜度: O(n) - HashMap 儲存
class Solution {
    fun interchangeableRectangles(rectangles: Array<IntArray>): Long {
        val map = HashMap<Long, Long>()

        for ((w, h) in rectangles) {
            val g = gcd(w, h)
            // 用一個 Long 編碼最簡分數，避免用 Pair
            val key = (w / g).toLong() * 100_001 + (h / g).toLong()
            map[key] = (map[key] ?: 0L) + 1L
        }

        var pairs = 0L
        for (count in map.values) {
            pairs += count * (count - 1) / 2
        }
        return pairs
    }

    private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}

⭐2: HashMap + GCD (One Pass)#

  • 概念: 邊遍歷邊累加配對數：加入新矩形時，它與 map 中已有的相同比例矩形都能配對
  • 時間複雜度: O(n log(max(w,h))) - GCD 計算
  • 空間複雜度: O(n) - HashMap 儲存
class Solution {
    fun interchangeableRectangles(rectangles: Array<IntArray>): Long {
        val map = HashMap<Long, Long>()
        var pairs = 0L

        for ((w, h) in rectangles) {
            val g = gcd(w, h)
            val key = (w / g).toLong() * 100_001 + (h / g).toLong()
            val count = map.getOrDefault(key, 0L)
            pairs += count
            map[key] = count + 1
        }

        return pairs
    }

    private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}

避免使用浮點數 width.toDouble() / height 作為 HashMap key，因為浮點數精度問題可能導致相同比例被判為不同。用 GCD 化簡為最簡分數是安全的做法。

🔑 Takeaways#

  • Pattern: 分組配對計數 -> HashMap 統計 + C(n,2) 或 One-Pass 累加
  • 關鍵技巧: 比例問題用 GCD 最簡分數取代浮點數比較；配對數的 One-Pass 累加避免二次遍歷