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

题目如下

数据范围

示例

注意到n和m的长度最长达到10的5次方所以时间复杂度为n方的必然超时。
因为题目要求我们返回每个位置的spell对应的有效对数所以我们只需要找到第一个有效的药水就行，这里可以先对potions排序随后使用二分查找把时间复杂度压到nlogn就不会超时。

通过代码

class Solution {
public:int findl(vector<int>& nums,long long v,long long target){int n = nums.size();int l = 0,r = n - 1;int mid = (l + r) / 2;while(l < r){if(v * nums[mid] >= target){r = mid;}else{l = mid + 1;}mid = (l + r) / 2;}if(v * nums[l] < target)return 0;return n - l;}vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {int n = spells.size(); sort(potions.begin(),potions.end());vector<int> ans;for(int i = 0;i < n;i++){ans.emplace_back(findl(potions,spells[i],success));}return ans;}
};