2300. Successful Pairs of Spells and Potions

Leetcode link

题目简介

题目给了 spells 与 potions 两个数组还有一个 number success，要求针对每一个 spells 中的元素 spells[i]，有多少个 potions 的元素 potions[j] 符合：spells[i] * potions[j] >= success

解题思路

针对题目要求，我们可以对 potions 做排序后，遍历当前 spells ，针对每一个 spell 用 binary search 找出符合题目要求的最小的 potions[j] 的下标 j

然后用 potions.length - j 就可以得出基于当前 spell 符合条件的 potion 有多少个了

Javascript

/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
var successfulPairs = function (spells, potions, success) {
    potions.sort((a, b) => a - b)
    const res = []

    spells.forEach(s => {
        const idx = binarySearch(potions, s, success)
        const count = potions.length - idx
        res.push(count)
    })
    return res
};

const binarySearch = (arr, multiples, target) => {
    let left = 0
    let right = arr.length

    while (left < right) {
        let mid = (left + right) >> 1
        if (arr[mid] * multiples >= target) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}