咒语和药水的成功对数

难度: Medium

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度相乘如果 大于等于 success ，那么它们视为一对成功的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的药水数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

提示：

n == spells.length
m == potions.length
1 <= n, m <= 10⁵
1 <= spells[i], potions[i] <= 10⁵
1 <= success <= 10¹⁰

Submission

运行时间: 154 ms

内存: 36.2 MB

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        m = len(potions)
        success -= 1
        return [m - bisect_right(potions, success//x) for x in spells]

Explain

首先对药水数组进行排序，以便使用二分查找来快速确定符合条件的药水数量。对于每个咒语，计算需要的最小药水强度，即 success 除以咒语的强度向下取整。使用二分查找确定该最小强度在排序后的药水数组中的位置，从而快速统计出能够与该咒语成功组合的药水数量。

时间复杂度: O(m log m + n log m)

空间复杂度: O(log m)

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()  # 对药水数组进行排序
        m = len(potions)  # 药水数组的长度
        success -= 1  # 由于是大于等于，将success减1简化计算
        return [m - bisect_right(potions, success//x) for x in spells]  # 对每个咒语计算符合条件的药水数目，使用二分查找确定位置

Explore

对药水数组进行排序是为了能够使用二分查找算法。二分查找算法需要在一个已排序的数组中进行，可以大幅提高效率，从O(n)的线性查找降低到O(log n)的对数时间复杂度。这样在处理每个咒语时，能够快速找到满足条件的药水的数量。

在已排序的药水数组中，`bisect_right`函数用于查找某个元素的插入位置，而这个位置是所有当前元素小于或等于这个插入值的所有元素之后。通过计算`bisect_right(potions, success//spell)`，我们得到的是第一个大于`success//spell`的药水位置。因此，从这个位置到数组结束的部分，都是满足条件的药水，即药水强度大于等于所需的最小强度。通过数组长度减去这个位置，我们可以直接得到符合条件的药水数量。

这种操作实际上是为了处理题目中的大于等于条件。在不减1的情况下，我们需要找的是大于等于`success/spell`的最小位置。减1后变为查找大于`success/spell - 1`的最小位置，这仍然符合我们找到大于等于`success/spell`的药水的目的，因此不会导致计算结果的偏差，而是简化了条件的处理。

如果药水数组中包含重复元素，使用`bisect_right`函数仍然可以正确工作。这个函数会返回所有相等值中最右侧的索引加一的位置。这意味着，即便数组中有重复的药水强度，我们仍然可以准确地定位到第一个大于所需最小强度的药水位置，从而计算出所有大于等于这个强度的药水的数量。