2300. Successful Pairs of Spells and Potions
给定两个阵列spells和points,前者表示多个咒语的强度,后者表示多个药剂的强度,若
咒语和药剂相乘大于success则这一组咒语和药剂配对成功,返回一个长度为spells的阵列
pairs,其中 pairs[i] 是能与第 i 个咒语配对成功的药剂数量。
Example:
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.
思路:
1.最简单的方法就是两个阵列相互配对并计算数量,但是咒语和药剂的长度很大这样做
肯定会吃TLE。
2.我们可以先把药剂的强度排序好,每个咒语使用二分搜索找到最小且满足success的
药剂,这样这个索引的右边全部都是配对成功的药剂,若potions.length = n
满足数量就会是 n - index,如果最右边(最大)的药剂和咒语不满足则二分搜索直接
返回n不用继续找寻。
Java Code: