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

对数"/>

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

​​题目来源：

        leetcode题目，网址：2300. 咒语和药水的成功对数 - 力扣（LeetCode）

解题思路：

       将 potions 数组排序后二分查找能够满足要求的最小值即可。

解题代码：

class Solution {
public:vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {vector<int> res;sort(potions.begin(),potions.end());for(int i=0;i<spells.size();i++){long minPotion=success/spells[i]+(success%spells[i]==0?0:1);res.push_back(getNum(potions,minPotion));}return res;}int getNum(vector<int>& potions,long minPotion){int start=0;int end=potions.size()-1;if(potions[start]>=minPotion){return end-start+1;}start++;while(start<=end){int mid=start+(end-start)/2;if(potions[mid]>=minPotion && potions[mid-1]<minPotion){return potions.size()-mid;}else if(potions[mid]>=minPotion){end=mid-1;}else{start=mid+1;}}return 0;}
};

总结：

        注意边界条件。

        官方题解给出了两种 解法。第一种是二分。第二种双指针，是将两个数组都排序后使用双指针查找，然后再按原来的顺序输出。

        C++ upper_bound(begin,end,num) 从数组的begin 位置到 end-1 位置二分查找第一个大于num 的数字。

        C++ lower_bound(begin,end,num) 从数组的begin 位置到 end-1 位置二分查找第一个小于等于 num 的数字。