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 是一个数组，如果将它排序，可以通过二分查找快速找到第一个满足条件的药水索引，进而计算成功的药水数量。

1. 首先对 potions 数组进行升序排序。
2. 对于每个咒语 spells[i]：

• 利用二分查找计算成功所需的最低药水值 success / spells[i]。
• 在 potions 中找到第一个大于等于最低药水值的药水索引。
• 成功配对药水数量为从该索引开始到数组末尾的药水数量。

3. 对每个咒语重复上述过程，得到每个咒语的成功配对药水数量，返回结果数组。

复杂度分析

• 时间复杂度：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+	🟠	🀄️ 🔗