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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* @Author: LetMeFly
* @Date: 2023-11-10 14:17:25
* @LastEditors: LetMeFly
* @LastEditTime: 2023-11-10 14:23:41
*/
typedef long long ll;
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, ll success) {
sort(potions.begin(), potions.end());
for (int& t : spells) {
ll toFind = success / t;
if (toFind * t < success) {
toFind++;
}
t = potions.end() - lower_bound(potions.begin(), potions.end(), toFind);
}
return spells;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
Author: LetMeFly
Date: 2023-11-10 14:25:21
LastEditors: LetMeFly
LastEditTime: 2023-11-10 14:28:30
'''
# from typing import List
# from bisect import bisect_left

class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort()
for i in range(len(spells)):
toFind = success // spells[i]
if toFind * spells[i] < success:
toFind += 1
spells[i] = len(potions) - bisect_left(potions, toFind)
return spells

查找范围小优化+不进行类型转换小优化

上述有两个可以优化的地方:

  1. 确定$toFind$的值,实质上就是$\lceil success / t\rceil$
  2. 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
* @Author: LetMeFly
* @Date: 2025-10-08 21:37:50
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-10-08 22:17:48
*/
/*
a * b >= success
a >= success/b
s b s/b a
6 2 3 3
6 3 2 2
6 4 1.5 2
6 5 1.x 2
a >= ⌈s/b⌉
a >= ⌊(s+b-1)/b⌋
*/
typedef long long ll;
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end());
for (int& s : spells) {
ll toFind = (success + s - 1) / s;
if (toFind > 100000) {
s = 0;
} else {
s = potions.end() - lower_bound(potions.begin(), potions.end(), toFind);
}
}
return spells;
}
};

查找范围小优化

上述有一个可以优化的地方:

$\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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
* @Author: LetMeFly
* @Date: 2025-10-08 21:37:50
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-10-08 22:21:04
*/
/*
a * b >= success
a >= success/b
s b s/b a
6 2 3 3
6 3 2 2
6 4 1.5 2
6 5 1.x 2
a >= ⌈s/b⌉
a >= ⌊(s+b-1)/b⌋
a >= ⌊(s-1)/b⌋+1
a > ⌊(s-1)/b⌋
*/
typedef long long ll;
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end());
success -= 1; // 提前-1后面不用每次都-1了
for (int& s : spells) {
ll target = success / s;
if (target > 100000) {
s = 0;
} else {
s = potions.end() - upper_bound(potions.begin(), potions.end(), target);
}
}
return spells;
}
};

(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.咒语和药水的成功对数/
作者
发布于
2023年11月10日
许可协议