互联网企业网站设计技成培训网

题目：

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为n的整数数组 pairs，其中 pairs[i]是能跟第 i 个咒语成功组合的药水数目。

思路：

转化为经典二分查找问题，套灵神模板。

代码：

class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {Arrays.sort(potions);int ans[] = new int[spells.length];for (int i = 0; i < spells.length; i++) {int x = spells[i];long y = (success - 1) / x + 1;int start = lowerBound(potions, y);ans[i] = potions.length - start;}return ans;}private int lowerBound(int[] nums, long target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}
}

性能：