跳至主要內容

2300. 咒语和药水的成功对数


2300. 咒语和药水的成功对数

🟠   🔖  数组 双指针 二分查找 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给你两个正整数数组 spellspotions ,长度分别为 nm ,其中 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 中找到第一个大于等于最低药水值的药水索引。
  • 成功配对药水数量为从该索引开始到数组末尾的药水数量。
  1. 对每个咒语重复上述过程,得到每个咒语的成功配对药水数量,返回结果数组。

复杂度分析

  • 时间复杂度O((m + n) * log m),其中 nspells.length, mpotions.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+🟠🀄️open in new window 🔗open in new window
2389和有限的最长子序列贪心 数组 二分查找 2+🟢🀄️open in new window 🔗open in new window
2410运动员和训练师的最大匹配数[✓]贪心 数组 双指针 1+🟠🀄️open in new window 🔗open in new window