Skip to content

Latest commit

 

History

History
185 lines (147 loc) · 6.91 KB

2300.md

File metadata and controls

185 lines (147 loc) · 6.91 KB
title description keywords
2300. 咒语和药水的成功对数
LeetCode 2300. 咒语和药水的成功对数题解，Successful Pairs of Spells and Potions，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
2300. 咒语和药水的成功对数
咒语和药水的成功对数
Successful Pairs of Spells and Potions
解题思路
数组
双指针
二分查找
排序

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

🟠 Medium  🔖  数组 双指针 二分查找 排序  🔗 力扣 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 least success.

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

复杂度分析

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