Leetcode.2001 可互换矩形的组数

题目链接

Leetcode.2001 可互换矩形的组数 Rating ： 1436

题目描述

用一个下标从 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<=1051 <= n <= 10^51<=n<=105
• $rectangles[i].length==2$
• 1<=widthi,heighti<=1051 <= widthi, heighti <= 10^51<=widthi,heighti<=105

解法：数论

我们先将 $rectangles[i]=[widthi,heighti]$ 中的 $widthi/heighti$ 化简为最简形式。

故让 $widthi和heighti$ 都除以它们的最大公约数，即 $gcd(widthi,heighti)$。

因为 1<=widthi,heighti<=1051 <= widthi, heighti <= 10^51<=widthi,heighti<=105，所以我们可以随便使用一个 >105>10^5>105 的数 $BASE$ 来将这两个数映射成一个数。比如，我们设置 BASE=106BASE = 10^6BASE=106，那么 $widthi和heighti$ 就可以映射成一个数 $widthi\ast BASE+heighti$。

我们用哈希表$cnt$记录相同数的个数。

对于$widthi和heighti$ ，我们讨论 $cnt[widthi\ast BASE+heighti]$ 的数量：

• $cnt[widthi\ast BASE+heighti]=1$,说明只有一个矩阵，不能互换，答案是0；
• $cnt[widthi\ast BASE+heighti]=2$,说明只有两个相同矩阵，只有1对能互换；
• $cnt[widthi\ast BASE+heighti]=3$,说明只有3个相同矩阵，只有3对能互换；
• $cnt[widthi\ast BASE+heighti]=4$,说明只有4个相同矩阵，只有6对能互换；
• …
• $cnt[widthi\ast BASE+heighti]=n$,说明只有n个相同矩阵，只有$(1+n-1)\ast (n-1)/2$对能互换；

时间复杂度： $O(nlog(max(e[0],e[1])))$

C++代码：

using LL = long long;
const LL BASE = 1e6;class Solution {
public:long long interchangeableRectangles(vector<vector<int>>& r) {int n =  r.size();unordered_map<LL,int> cnt;for(auto &e:r){int g = gcd(e[0],e[1]);e[0] /= g;e[1] /= g;cnt[e[0] * BASE + e[1]]++;}LL ans = 0;for(auto [_,v]:cnt){if(v < 2) continue;ans += (1 + v - 1) * 1LL * (v - 1) / 2;}return ans;}
};