可互换矩形的组数
难度:
标签:
题目描述
代码结果
运行时间: 144 ms, 内存: 61.5 MB
// 思路:
// 使用Java Stream API来实现与上面相同的逻辑。
// 我们将矩形转换为宽高比,并计算每个比率的数量,然后计算成对的可互换矩形。
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class Solution {
public long interchangeableRectangles(int[][] rectangles) {
Map<Double, Long> ratioCount = Arrays.stream(rectangles)
.map(rect -> (double) rect[0] / rect[1])
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
return ratioCount.values().stream()
.mapToLong(count -> count * (count - 1) / 2)
.sum();
}
}
解释
方法:
The solution leverages a hash map (Counter) to record the frequency of each unique width-to-height ratio encountered among the rectangles. Instead of using the raw division result, which could suffer from floating-point precision issues, it implicitly uses the ratio of width to height. For each unique ratio found, if there are 'x' rectangles with that ratio, the number of interchangeable pairs among these rectangles can be calculated using the combination formula 'x choose 2', which simplifies to x*(x-1)/2. This approach counts all such pairs across different unique ratios.
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在计算宽高比时,为什么选择使用`w/h`而不是其他形式,例如`h/w`或是两者的差异?
▷🦆
如何确保`w/h`的计算中不会受到Python浮点数精度问题的影响?
▷🦆
在使用Counter计算频率时,是否有可能出现某些比例因为精度问题而被错误地认为不相等?
▷🦆
题解中提到使用组合公式`x*(x-1)/2`来计算可互换矩形的组数,为什么这种方法是适用的?
▷