2300 咒语和药水的成功对数

题目描述#

给定一个spell和potion，长度分别为n和m

有一个success，需要做到咒语和药水的能量强度相乘大于success

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

思路#

先对potion进行排序，然后使用二分算法

当循环结束时，left 指向第一个使得 spell[i] * potion >= success 的位置，也就是成功配对的最小下标。因此成功配对的数量应为：

ans[i] = potions.length - left;

代码#

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 left = 0;
            int right = potions.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                long power = 1L * spells[i] * potions[mid];
                if (power >= success) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            ans[i] = potions.length - left;
        }
        return ans;
    }
}