題目描述:
給定 n 個矩形,每個矩形以 [width, height] 表示。兩個矩形「可互換」的條件是它們的寬高比相同,即 width_i / height_i == width_j / height_j。求可互換的矩形對數。
解題思路:
gcd(width, height),然後用 (width/gcd, height/gcd) 作為鍵。c 個矩形,可組成 c * (c - 1) / 2 對。時間複雜度:O(n log M) — 遍歷所有矩形,每個求 gcd 需要 O(log M)(M 為寬高最大值)。
空間複雜度:O(n) — 雜湊表最多儲存 n 個不同的比例。
1. Create hash map: (reduced_width, reduced_height) -> count 2. For each rectangle (w, h): a. g = gcd(w, h) b. Increment map[(w/g, h/g)] 3. For each group with count c: a. Add c * (c - 1) / 2 to answer 4. Return answer
浮點數法 O(n):直接用 double 型別計算 width / height 作為鍵。簡單但有精度風險,不建議在大數值場景使用。
排序法 O(n log n):將所有矩形按最簡分數排序,然後線性掃描計數連續相同分數的數量。時間複雜度略高但不需雜湊表。
[l, w, h],兩個長方體可互換的條件是比例完全相同,做法如何推廣?c 很大時 c*(c-1) 可能溢出)