class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
}
};
2300. 咒语和药水的成功对数
给你两个正整数数组 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.lengthm == potions.length1 <= n, m <= 1051 <= spells[i], potions[i] <= 1051 <= success <= 1010原站题解
javascript 解法, 执行用时: 236 ms, 内存消耗: 70 MB, 提交时间: 2023-11-10 07:21:48
/**
* @param {number[]} spells
* @param {number[]} potions
* @param {number} success
* @return {number[]}
*/
var successfulPairs = function (spells, potions, success) {
potions.sort((a, b) => a - b);
for (let i = 0; i < spells.length; i++) {
const target = Math.ceil(success / spells[i]);
spells[i] = potions.length - lowerBound(potions, target);
}
return spells;
};
var lowerBound = function (nums, target) {
let left = -1, right = nums.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
const mid = left + ((right - left) >> 1);
if (nums[mid] >= target) {
right = mid; // 范围缩小到 (left, mid)
} else {
left = mid; // 范围缩小到 (mid, right)
}
}
return right; // 或者 left+1
}
rust 解法, 执行用时: 40 ms, 内存消耗: 3.9 MB, 提交时间: 2023-11-10 07:21:28
impl Solution {
pub fn successful_pairs(mut spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
potions.sort_unstable();
let last = potions[potions.len() - 1] as i64;
for x in spells.iter_mut() {
let target = (success - 1) / *x as i64;
if target < last { // 防止 i64 转成 i32 溢出
*x = (potions.len() - Self::upper_bound(&potions, target as i32)) as i32;
} else {
*x = 0;
}
}
spells
}
fn upper_bound(nums: &Vec<i32>, target: i32) -> usize {
let mut left = 0;
let mut right = nums.len();
while left < right {
let mid = (left + right) / 2;
if nums[mid] > target {
right = mid;
} else {
left = mid + 1;
}
}
left
}
}
java 解法, 执行用时: 46 ms, 内存消耗: 55.4 MB, 提交时间: 2023-09-25 15:19:10
class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
int m = spells.length;
int n = potions.length;
int[] res = new int[m];
int i = 0;
while (i < m) {
long spell = (long) spells[i];
int left = 0;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (spell * potions[mid] < success) {
left = mid + 1;
} else {
right = mid;
}
}
res[i] = n - left;
i++;
}
return res;
}
}
golang 解法, 执行用时: 188 ms, 内存消耗: 9.5 MB, 提交时间: 2023-09-25 15:18:44
func successfulPairs(spells, potions []int, success int64) []int {
sort.Ints(potions)
for i, x := range spells {
spells[i] = len(potions) - sort.SearchInts(potions, (int(success)-1)/x+1)
}
return spells
}
cpp 解法, 执行用时: 244 ms, 内存消耗: 95.3 MB, 提交时间: 2023-09-25 15:18:10
class Solution {
public:
vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success) {
sort(potions.begin(), potions.end());
for (auto &x : spells)
x = potions.end() - upper_bound(potions.begin(), potions.end(), (success - 1) / x);
return spells;
}
};
python3 解法, 执行用时: 244 ms, 内存消耗: 36.8 MB, 提交时间: 2023-09-25 15:17:52
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort()
return [len(potions) - bisect_right(potions, (success - 1) // x) for x in spells]