Day66 | 灵神 | 二分查找：咒语和药水的成功对数

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

2300. 咒语和药水的成功对数 - 力扣（LeetCode）

思路：

这个题目还挺好想的

其实还是在数组里面去找左边界而已，只是在外面多套了一层数组的遍历

遍历spells数组，然后里面套找左边界的二分查找就行，查找options数组里面的满足条件的左边界，找到之后求出左边界到数组末尾这个区间的长度就行

记得先排序options，因为只有有序我们才可以使用二分查找

时间复杂度是遍历数组spells，二分查找options，一共O(nlogm)。再加上排序的时间复杂度O(mlogm)

时间复杂度= O(nlogm)+O(mlogm)=O((n+m)logm)

如果不太会写左边界的二分查找，可以看看昨天的博客：

Day65 | 灵神 | 二分查找：红蓝染色法-CSDN博客

完整代码：

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
class Solution {
public:
    bool check(long long a,long long b,long long c)
    {
        if(a*b>=c)
            return true;
        else
            return false;
    }
    int lower_bound(int spells,vector<int>& nums,long long target)
    {
        int l=0,r=nums.size();
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(check(nums[mid],spells,target))
                r=mid;
            else    
                l=mid+1;
        }
        return l;
    }
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> pairs;
        int single_pairs=0;
        sort(potions.begin(),potions.end());
        for(int i=0;i<spells.size();i++)
        {
            single_pairs=potions.size()-lower_bound(spells[i],potions,success);
            pairs.push_back(single_pairs);
        }
        return pairs;
    }
};