leetcode
leetcode 2001 ~ 2050
咒语和药水的成功对数

咒语和药水的成功对数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么在处理题目时首先选择对药水数组进行排序?
对药水数组进行排序是为了能够使用二分查找算法。二分查找算法需要在一个已排序的数组中进行,可以大幅提高效率,从O(n)的线性查找降低到O(log n)的对数时间复杂度。这样在处理每个咒语时,能够快速找到满足条件的药水的数量。
🦆
解释中提到的`bisect_right`函数是如何帮助确定符合条件的药水数量的?
在已排序的药水数组中,`bisect_right`函数用于查找某个元素的插入位置,而这个位置是所有当前元素小于或等于这个插入值的所有元素之后。通过计算`bisect_right(potions, success//spell)`,我们得到的是第一个大于`success//spell`的药水位置。因此,从这个位置到数组结束的部分,都是满足条件的药水,即药水强度大于等于所需的最小强度。通过数组长度减去这个位置,我们可以直接得到符合条件的药水数量。
🦆
你在算法中将`success`减1以简化计算,这种操作是否可能导致计算结果的偏差?
这种操作实际上是为了处理题目中的大于等于条件。在不减1的情况下,我们需要找的是大于等于`success/spell`的最小位置。减1后变为查找大于`success/spell - 1`的最小位置,这仍然符合我们找到大于等于`success/spell`的药水的目的,因此不会导致计算结果的偏差,而是简化了条件的处理。
🦆
算法中使用二分查找确定最小强度药水的位置,但是如果药水数组包含重复元素会怎样影响查找结果?
如果药水数组中包含重复元素,使用`bisect_right`函数仍然可以正确工作。这个函数会返回所有相等值中最右侧的索引加一的位置。这意味着,即便数组中有重复的药水强度,我们仍然可以准确地定位到第一个大于所需最小强度的药水位置,从而计算出所有大于等于这个强度的药水的数量。

相关问题