题目描述
平台：LeetCode
题号：2300
给你两个正整数数组 spells 和 potions，长度分别为 n 和 m，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
同时给你一个整数 success。一个咒语和药水的能量强度相乘如果大于等于 success，那么它们视为一对成功的组合。
请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。
示例 1：
代码语言：javascript复制输入：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：
代码语言：javascript复制输入：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] 。
提示：
排序 二分
为了方便，我们将 spells 记为 a，将 potions 记为 b，将 success 记为 t。
对于每个
，有多少个
满足
，等价于问数组 b 中值大于等于
的个数，这容易让我们想到先对数组 b 排升序，再通过二分找到满足该条件的最小下标，从该下标到数组结尾，均为满足条件的
。
Java 代码：
代码语言：javascript复制class Solution {
public int[] successfulPairs(int[] a, int[] b, long t) {
int n = a.length, m = b.length;
int[] ans = new int[n];
Arrays.sort(b);
for (int i = 0; i < n; i ) {
double cur = t * 1.0 / a[i];
int l = 0, r = m - 1;
while (l < r) {
int mid = l r >> 1;
if (b[mid] >= cur) r = mid;
else l = mid 1;
}
if (b[r] * 1L * a[i] >= t) ans[i] = m - r;
}
return ans;
}
}
Python 代码：
代码语言：javascript复制class Solution:
def successfulPairs(self, a: List[int], b: List[int], t: int) -> List[int]:
# n, m = len(a), len(b)
# b.sort()
# ans = [0] * n
# for i in range(n):
# cur = t / a[i]
# l, r = 0, m - 1
# while l < r:
# mid = l r >> 1
# if b[mid] >= cur: r = mid
# else: l = mid 1
# ans[i] = m - r if b[r] * a[i] >= t else 0
# return ans
b.sort()
return [len(b) - bisect_left(b, t / x) for x in a]
C 代码：
代码语言：javascript复制class Solution {
public:
vector<int> successfulPairs(vector<int>& a, vector<int>& b, long long t) {
// int n = a.size(), m = b.size();
// vector<int> ans(n);
// sort(b.begin(), b.end());
// for (int i = 0; i < n; i ) {
// double cur = t * 1.0 / a[i];
// int l = 0, r = m - 1;
// while (l < r) {
// int mid = l r >> 1;
// if (b[mid] >= cur) r = mid;
// else l = mid 1;
// }
// if (b[r] * 1L * a[i] >= t) ans[i] = m - r;
// }
// return ans;
int n = a.size(), m = b.size();
vector<int> ans(n);
sort(b.begin(), b.end());
for (int i = 0; i < n; i ) ans[i] = b.end() - lower_bound(b.begin(), b.end(), t * 1.0 / a[i]);
return ans;
}
};
TypeScript 代码：
代码语言：javascript复制function successfulPairs(a: number[], b: number[], t: number): number[] {
const n = a.length, m = b.length;
const ans = new Array(n).fill(0);
b.sort((a,b)=>a-b);
for (let i = 0; i < n; i ) {
const cur = t * 1.0 / a[i];
let l = 0, r = m - 1;
while (l < r) {
const mid = l r >> 1;
if (b[mid] >= cur) r = mid;
else l = mid 1;
}
if (b[r] * a[i] >= t) ans[i] = m - r;
}
return ans;
};
- 时间复杂度：对数组
b排序的复杂度为
；构建答案时，每次在值域
范围内进行二分，复杂度为
。整体复杂度为
- 空间复杂度：
