Successful Pairs Of Spells And Potions

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

分析

排序药水数组：
- 为了快速确定满足条件的药水，我们对药水数组 potions 进行升序排序
二分查找：
- 对于每个咒语 spells[i]，计算所需药水的最小能量值：target = (success + spells[i] - 1) / spells[i]
- 使用二分查找找到第一个大于等于 target 的药水位置 pos
- 满足条件的药水数量为 m - pos，其中 m 是药水数组的长度
返回结果：
- 对每个咒语计算成功组合的药水数量，并存储在结果数组 res 中

时间复杂度

药水数组排序：O(mlogm)
对每个咒语进行二分查找：O(nlogm)

总时间复杂度：O(mlogm + nlogm)

空间复杂度

空间复杂度为 O(n)

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


class Solution {
public:
    // 二分查找：找到第一个大于等于 target 的药水位置
    int search(std::vector<int>& potions, long long target)
    {
        int l = 0, r = potions.size();
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (potions[mid] >= target)
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }

    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success)
    {
        int n = spells.size(), m = potions.size();
        std::sort(potions.begin(), potions.end()); // 排序药水数组
        std::vector<int> res(n);
        for (int i = 0; i < n; ++i)
        {
            // 计算当前咒语的 target 值
            int pos = search(potions, (success + spells[i] - 1) / spells[i]);
            res[i] = m - pos; // 成功组合数量
        }
        return res;
    }
};