咒语和药水的成功对数
难度:
标签:
题目描述
代码结果
运行时间: 154 ms, 内存: 36.2 MB
/*
题目思路:
1. 使用 Java Stream 遍历 spells 数组中的每个元素。
2. 对于每个元素,过滤出 potions 中与之组合后能量强度大于等于 success 的药水数量。
3. 将这些数量存储在结果数组 pairs 中。
*/
import java.util.Arrays;
public class SuccessfulPairsStream {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
return Arrays.stream(spells)
.map(spell -> (int) Arrays.stream(potions)
.filter(potion -> (long) spell * potion >= success)
.count())
.toArray();
}
}
解释
方法:
首先对药水数组进行排序,以便使用二分查找来快速确定符合条件的药水数量。对于每个咒语,计算需要的最小药水强度,即 success 除以咒语的强度向下取整。使用二分查找确定该最小强度在排序后的药水数组中的位置,从而快速统计出能够与该咒语成功组合的药水数量。
时间复杂度:
O(m log m + n log m)
空间复杂度:
O(log m)
代码细节讲解
🦆
为什么在处理题目时首先选择对药水数组进行排序?
▷🦆
解释中提到的`bisect_right`函数是如何帮助确定符合条件的药水数量的?
▷🦆
你在算法中将`success`减1以简化计算,这种操作是否可能导致计算结果的偏差?
▷🦆
算法中使用二分查找确定最小强度药水的位置,但是如果药水数组包含重复元素会怎样影响查找结果?
▷