LeetCode 2001. Number of Pairs of Interchangeable Rectangles

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [widthi, heighti] denotes the width and height of the ith rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if widthi/heighti == widthj/heightj (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

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.

其实只要会最大公约数这个函数即可，这样15 30，跟10 20这一组就是同一类的，然后map存储每个的数量，最后用排列算出来，返回；

Constraints:

• n == rectangles.length

• 1 <= n <= 105

• rectangles[i].length == 2

• 1 <= widthi, heighti <= 105

Runtime: 123 ms, faster than 8.98% of Java online submissions for Number of Pairs of Interchangeable Rectangles.

Memory Usage: 93.1 MB, less than 34.28% of Java online submissions for Number of Pairs of Interchangeable Rectangles.