dw做网站注册页代码,网站建设模板源代码,海北公司网站建设价格低,泰州seo公司题目#xff1a;
给你两个正整数数组 spells 和 potions #xff0c;长度分别为 n 和 m #xff0c;其中 spells[i] 表示第 i 个咒语的能量强度#xff0c;potions[j] 表示第 j 瓶药水的能量强度。
同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等…题目
给你两个正整数数组 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;}
}
性能
