用排序 + 二分查找快速统计每个咒语对应的成功药水数量:先将药水数组排序,再对每个咒语计算所需的最小药水强度,通过二分查找定位该强度的位置,从而得到符合条件的药水数量。
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end()); //排序
vector<int> ans;
for (int spell : spells) {
// 计算当前咒语所需的最小药水强度
double target = success * 1.0 / spell;
// 找到第一个大于等于target的药水位置
auto it = lower_bound(potions.begin(), potions.end(), target);
// 符合条件的药水数量 = 数组总长度 - 该位置的下标
ans.push_back(potions.end() - it);
}
return ans;
}
};

京公网安备 11010502036488号