2300.咒语和药水的成功对数:二分查找(附(lower/upper)_bound库函数大于小于个数查找表)
【LetMeFly】2300.咒语和药水的成功对数:二分查找(附(lower/upper)_bound库函数大于小于个数查找表)
力扣题目链接:https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/
给你两个正整数数组 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 <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010
解题方法:二分查找
我们首先将“毒药”数组从小到大排序,那么对于咒语$i$,计算出其想要达到$success$所需的最小毒药强度$toFind$,接着二分查找$toFind$的位置即可。
- 时间复杂度$O(n\log n)$,其中$n=len(potions)$
- 空间复杂度$O(log n)$
AC代码
C++
1 |
|
Python
1 |
|
查找范围小优化+不进行类型转换小优化
上述有两个可以优化的地方:
- 确定$toFind$的值,实质上就是$\lceil success / t\rceil$
lower_bound(vector<int>::iterator, vector<int>::iterator, long long)
会在比较的过程中将每个int自动转为long long
类型,有一丢丢耗时;可以在$toFind$明显超出毒药毒性数据范围时直接返回$0$。
以上。
- 时间复杂度$O(n\log n)$,其中$n=len(potions)$
- 空间复杂度$O(log n)$
AC代码
C++
1 |
|
查找范围小优化
上述有一个可以优化的地方:
$\geq\lceil \frac{success}{t}\rceil$ ⇔ $\geq\lfloor\frac{success+t-1}{t}\rfloor$ ⇔ $\geq\lfloor\frac{success-1}{t}\rfloor+1$
由于所涉及的数据都是整数,所以有$\geq\lfloor\frac{success-1}{t}\rfloor+1$ ⇔ $\gt \lfloor\frac{success-1}{t}\rfloor$
以上。
- 时间复杂度$O(n\log n)$,其中$n=len(potions)$
- 空间复杂度$O(log n)$
AC代码
C++
1 |
|
(lower/upper)_bound库函数含义、大于小于个数查找表
(lower/upper)_bound库函数含义
函数 | 返回的位置含义 |
---|---|
lower_bound(a.begin(), a.end(), x) |
第一个 ≥ x 的元素的位置 |
upper_bound(a.begin(), a.end(), x) |
第一个 > x 的元素的位置 |
查找(大于等于/大于/小于/小于等于)x的元素的个数
条件 | 表达式 | 含义 |
---|---|---|
≥ x | a.end() - lower_bound(a.begin(), a.end(), x) |
从 ≥x 开始到末尾 |
> x | a.end() - upper_bound(a.begin(), a.end(), x) |
从 >x 开始到末尾 |
≤ x | upper_bound(a.begin(), a.end(), x) - a.begin() |
从开头到 ≤x 结束 |
< x | lower_bound(a.begin(), a.end(), x) - a.begin() |
从开头到 <x 结束 |
End
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
2300.咒语和药水的成功对数:二分查找(附(lower/upper)_bound库函数大于小于个数查找表)
https://blog.letmefly.xyz/2023/11/10/LeetCode 2300.咒语和药水的成功对数/