2300. 咒语和药水的成功对数 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] 。
解题思路
输入： 给你两个正整数数组 spells 和 potions
输出： 返回当咒语和药水相乘之后得到新数组中大于 success 的数量有多少
本题属于二分查找类问题。
由于只需要求出大于 success 的数量，所以咒语和药水相乘后的新数组顺序是不固定的，因此我们可以将药水先排序方便后续二分
问题就变成了求一个有序数组中大于等于 target 的数量
我们可以求出第一个大于等于 target 的值的坐标 idx，也就是左边界
数组长度减去左边界 len(nums) - idx 就是数组中大于等于 target 的数量
为了减少多余的遍历，我们只需要将要相乘的咒语当成参数传入二分查找函数中即可
代码实现
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
# 二分查找函数，返回第一个使 spell * potion >= success 的 potion 下标
def lower_bound(nums, target, factor):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
# 如果当前乘积小于目标值，说明需要更大的 potion 值
if nums[mid] * factor < target:
left = mid + 1
else:
right = mid - 1
return left # 返回满足条件的最小下标
# 对 potions 排序以便二分查找
potions.sort()
n = len(potions)
res = []
# 遍历每个 spell，找出对应成功配对的 potion 个数
for spell in spells:
# 找到第一个使 spell * potion >= success 的位置
idx = lower_bound(potions, success, spell)
# 总成功配对数 = 满足条件的 potion 数量
res.append(n - idx)
return res/**
* @param {number[]} spells
* @param {number[]} potions
* @param {number} success
* @return {number[]}
*/
var successfulPairs = function(spells, potions, success) {
function lowerBound(nums, target, factor) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] * factor < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
const ans = [];
potions.sort((a, b) => a - b);
for (let s of spells) {
const idx = lowerBound(potions, success, s);
ans.push(potions.length - idx);
}
return ans;
};复杂度分析
时间复杂度：O(log n)
空间复杂度：O(1)