計數應用題 等比例矩形配對的數目 Leetcode #2001

這題的題目在這裡:

題目敘述

題目會給定一組輸入陣列，裡面每個參數分別代表矩形的寬和高。
如果有兩個矩形的寬/高的比例是相同的，代表這兩個矩形是等比例的。

要求我們計算，等比例的矩形pair總共有多少個?

測試範例

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.

約束條件

Constraints:

• n == rectangles.length
• 1 <= n <= 105
• rectangles[i].length == 2
• 1 <= widthi, heighti <= 105

演算法

除了第一直覺，雙層迴圈直接去模擬good pair的生成並且計數以外；這題還有一個高效率的排列組合作法。

基本上和前一題 good pair counting 那題九成像，換湯不換藥。都是任選兩個物品，可以構成一組pair。

唯一的小差別是:

前一題是 數字相同的兩個數字，構成一組good pair。

這一題是 寬/高 比例相同的兩個矩形，構成一組rectangle pair。

最後，還額外多提供一種等價的one-pass counting演算法，供讀者比較、參考。

程式碼 C(n, 2) 法

class Solution:
　def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
　　
　　rect_ratio = defaultdict(int)

　　# update occurrence of w/h ratio
　　for width, height in rectangles:
　　　cur_ratio = width / height
　　　rect_ratio[ cur_ratio ] += 1

　　# count the interchangeable rectangles by definition and C(n, 2) formula
　　counter = 0
　　for ratio, n in rect_ratio.items():
　　　
　　　counter += n * ( n-1 ) // 2

　　return counter

程式碼 one-pass的邊數邊算法

class Solution:
　def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
　　
　　rect_ratio = defaultdict(int)

　　counter = 0
　　for width, height in rectangles:

　　　cur_ratio = width / height

　　　# update occurrence of w/h ratio
　　　counter += rect_ratio[ cur_ratio ] 

　　　# count the interchangeable rectangles by definition 
　　　rect_ratio[ cur_ratio ] += 1

　　return counter

複雜度分析

時間複雜度:

O( n ) 建造字典掃描數字耗費O(n)，掃描字典內的數字也耗費O(n)。

空間複雜度:

O( n ) 字典大小最大和陣列一樣長，所佔用空間為O(n)。

關鍵知識點

觀察並且模擬幾個小範例，可以這種pair counting類的題目，背後的原理其實就是n個物品，任選兩個的方法數，可以由排列組合公式C(n, 2)計算得到答案。

強烈建議複習前面 good pair counting這題，其實原理都是相通的喔!

Reference:

[1] Python O(n) by ratio counting [w/ Comment] - Number of Pairs of Interchangeable Rectangles - LeetCode