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.
Constraints:
n == rectangles.length
1 <= n <= 105
rectangles[i].length == 2
1 <= widthi, heighti <= 105
Solution: Hashtable
Use aspect ratio as the key.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: long long interchangeableRectangles(vector<vector<int>>& rectangles) { long long ans = 0; unordered_map<long long, int> m; for (const auto& r : rectangles) { long long d = gcd(r[0], r[1]); ans += m[((r[0] / d) << 20) | (r[1] / d)]++; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment