【排序+二分】【数组】【2023-11-10】
我们首先对 points
进行升序排序,然后枚举 spells
中的 x
,需要找到在 points
中大于等于
⌈
s
u
c
c
e
s
s
x
⌉
\lceil{\frac {success}{x}} \rceil
⌈xsuccess⌉ 的数量。那我们找到在 points
中大于等于
⌈
s
u
c
c
e
s
s
x
⌉
\lceil{\frac {success}{x}} \rceil
⌈xsuccess⌉ 最小位置 idx
即可,这样在 points
中大于等于
⌈
s
u
c
c
e
s
s
x
⌉
\lceil{\frac {success}{x}} \rceil
⌈xsuccess⌉ 的数量就为 points.end() - idx
。使用 C++ 的库函数 lower_bound()
实现。自己实现在有序数组中查找大于等于指定元素的二分方法可以参考 【二分查找】几种基本题型,你会了吗?。
为什么要找在 points
中大于等于
⌈
s
u
c
c
e
s
s
x
⌉
\lceil{\frac {success}{x}} \rceil
⌈xsuccess⌉ 的数量?因为 x
和 points
中的 y
(某一瓶药水的能量强度)要满足:
x y > = s u c c e s s xy >= success xy>=success
找到满足上式的 y
的数量即为 x
对应的答案。上式即为
y
>
=
⌈
s
u
c
c
e
s
s
x
⌉
y >= \lceil{\frac {success}{x}} \rceil
y>=⌈xsuccess⌉。如果不明白上式是如何计算得到
y
>
=
⌈
s
u
c
c
e
s
s
x
⌉
y >= \lceil{\frac {success}{x}} \rceil
y>=⌈xsuccess⌉ 话,可以这样转换:
y > = 1.0 ∗ s u c c e s s / x y >= 1.0 * success / x y>=1.0∗success/x
这样就是数学中的除法运算,方便理解。
实现代码
class Solution {
public:
vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success) {
sort(potions.begin(), potions.end());
for (int &x : spells) {
long long target = (success + x - 1) / x;
x = potions.end() - lower_bound(potions.begin(), potions.end(), target);
}
return spells;
}
};
复杂度分析
时间复杂度:
O
(
m
l
o
g
m
+
n
l
o
g
m
)
O(mlogm+nlogm)
O(mlogm+nlogm),
m
m
m 为数组 points
的长度,
n
n
n 为数组 spells
的长度。
空间复杂度: O ( l o g m ) O(logm) O(logm)。
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort()
return [len(potions) - bisect_left(potions, success / x) for x in spells]
bisect_left
是 python3 中查找大于等于指定元素的函数。
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。