Tag

【排序+二分】【数组】【2023-11-10】

---

题目来源

2300. 咒语和药水的成功对数

---

解题思路

方法一：排序+二分

我们首先对 points 进行升序排序，然后枚举 spells 中的 x，需要找到在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 的数量。那我们找到在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 最小位置 idx 即可，这样在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 的数量就为 points.end() - idx。

为什么要找在 points 中大于等于 $\lceil \frac{success}{x}\rceil$ 的数量？因为 x 和 points 中的 y（某一瓶药水的能量强度）要满足：

$$xy>=success$$

找到满足上式的 y 的数量即为 x 对应的答案。上式即为 $x>=\lceil \frac{success}{x}\rceil$。

实现代码

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(mlogm+nlogm)$，$m$ 为数组 points 的长度，$n$ 为数组 spells 的长度。

空间复杂度：$O(logm)$。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。