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

Every day a Leetcode

题目来源：2300. 咒语和药水的成功对数

解法1：暴力

代码：

class Solution { public: vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success) { int n = spells.size(), m = potions.size(); vector<int> pairs(n, 0); for (int i = 0; i < n; i++) { int count = 0; for (const int &potion : potions) if ((long long)spells[i] * potion >= success) count++; pairs[i] = count; } return pairs; } };

结果：超时。

复杂度分析：

时间复杂度：O(n * m)，其中 n 是数组 spells 的长度，m 是数组 potions 的长度。

空间复杂度：O(1)。

解法2：二分查找

对于某一个咒语的能量，我们可以采用二分查找的方法来高效地找到符合条件的药水数量。

首先，我们将 potions 数组进行排序，以便能够利用有序性进行二分查找。然后，对于每个咒语 spells[i]，我们计算出目标值 target = ceil(1.0 * success / spells[i])，代表了在当前咒语强度下，药水需要达到的最低强度。接下来，我们使用「二分查找」来在数组 potions 中找到第一个大于等于 target 的元素的索引 index，进一步可以得到此时表示成功组合的药水数量为 m − index，其中 m 表示数组 potions 的长度。

代码：

class Solution { public: vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success) { int n = spells.size(), m = potions.size(); vector<int> pairs(n, 0); sort(potions.begin(), potions.end()); for (int i = 0; i < n; i++) { long long target = ceil(1.0 * success / spells[i]); int left = 0, right = m - 1; while (left <= right) { int mid = (left + right) / 2; if ((long long)spells[i] * potions[mid] >= success) right = mid - 1; else left = mid + 1; } pairs[i] = m - left; } return pairs; } };

结果：

复杂度分析：

时间复杂度：O(m * logm + n * logm)，其中 n 是数组 spells 的长度，m 是数组 potions 的长度。排序的时间复杂度为 O(m * logm)，一次二分查找的时间复杂度为 O(logm)，共 n 次，所有二分查找的总的时间复杂度为 O(n * logm)。

空间复杂度：O(logm)，其中 m 是数组 potions 的长度