题目链接

咒语和药水的成功对数

题目描述

注意点

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

解答思路

• 先将药水进行排序，然后二分查找找到某个咒语i和药水的能量强度相乘大于等于success的左边界left，res[i] = n - left

代码

class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {int m = spells.length;int n = potions.length;int[] res = new int[m];Arrays.sort(potions);for (int i = 0; i < m; i++) {int left = 0, right = n - 1;// 找到咒语和药水的能量强度相乘大于等于success的左边界while (left <= right) {int mid = left + (right - left >> 1);if ((long) spells[i] * potions[mid] >= success) {right = mid - 1;} else {left = mid + 1;}}res[i] = n - left;}return res;}
}

关键点

• 二分查找的思想