2300. 咒语和药水的成功对数
2300. 咒语和药水的成功对数
🟠 🔖 数组
双指针
二分查找
排序
🔗 力扣
LeetCode
题目
You are given two positive integer arrays spells
and potions
, of length n
and m
respectively, where spells[i]
represents the strength of the ith
spell and potions[j]
represents the strength of the jth
potion.
You are also given an integer success
. A spell and potion pair is considered successful if the product of their strengths is at leastsuccess
.
Return an integer arraypairs
of lengthn
wherepairs[i]
_is the number ofpotions that will form a successful pair with the _ith
spell.
Example 1:
Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10 ,15 ,20 ,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9 ,12 ,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.
Example 2:
Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24 ,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
- 2nd spell: 2 * [8,5,8] = [16 ,10,16]. 2 pairs are successful.
Thus, [2,0,2] is returned.
Constraints:
n == spells.length
m == potions.length
1 <= n, m <= 10^5
1 <= spells[i], potions[i] <= 10^5
1 <= success <= 1010
题目大意
给你两个正整数数组 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^5
1 <= spells[i], potions[i] <= 10^5
1 <= success <= 1010
解题思路
对于每个咒语 spells[i]
,需要找到满足 spells[i] * potions[j] >= success
的所有 potions[j]
。
可以将问题转化为:对于每个 spells[i]
,需要找到 potions[j] >= success / spells[i]
的药水数量。
potions
是一个数组,如果将它排序,可以通过二分查找快速找到第一个满足条件的药水索引,进而计算成功的药水数量。
- 首先对
potions
数组进行升序排序。 - 对于每个咒语
spells[i]
:
- 利用二分查找计算成功所需的最低药水值
success / spells[i]
。 - 在
potions
中找到第一个大于等于最低药水值的药水索引。 - 成功配对药水数量为从该索引开始到数组末尾的药水数量。
- 对每个咒语重复上述过程,得到每个咒语的成功配对药水数量,返回结果数组。
复杂度分析
- 时间复杂度:
O((m + n) * log m)
,其中n
是spells.length, m
是potions.length
:- 对
potions
排序的时间复杂度是O(m log m)
; - 对每个咒语执行二分查找的时间复杂度是
O(n log m)
;
- 对
- 空间复杂度:
O(1)
,排序和二分查找均为原地操作,使用了常数级的空间。
代码
/**
* @param {number[]} spells
* @param {number[]} potions
* @param {number} success
* @return {number[]}
*/
var successfulPairs = function (spells, potions, success) {
// 预先计算好 success / spells[i],避免重复计算
const arr = spells.map((i) => success / i);
const n = potions.length;
// 对 potions 进行升序排序
potions.sort((a, b) => a - b);
// 二分查找函数
const getPairs = (idx) => {
let left = 0,
right = n - 1;
while (left <= right) {
const mid = ((left + right) / 2) | 0;
if (potions[mid] >= arr[idx]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// left 是第一个满足条件的索引
// 返回成功配对数量
return left == n ? 0 : n - left;
};
// 遍历 spells,计算每个咒语的成功配对数量
return spells.map((_, idx) => getPairs(idx));
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
826 | 安排工作以达到最大收益 | 贪心 数组 双指针 2+ | 🟠 | 🀄️ 🔗 | |
2389 | 和有限的最长子序列 | 贪心 数组 二分查找 2+ | 🟢 | 🀄️ 🔗 | |
2410 | 运动员和训练师的最大匹配数 | [✓] | 贪心 数组 双指针 1+ | 🟠 | 🀄️ 🔗 |