2300. Successful Pairs of Spells and Potions - Medium

前往題目

想法

• 暴力解很直觀
• 可以先排序，這樣就可以用Binary Search找那個最弱的藥水

思路

1. 排序藥水，從大到小
2. 一個咒語一個咒語循環
3. 每個咒語都用二元搜尋去找第一個success的藥水，找到就可以知道總共有幾個藥水可以成功
4. 每個咒語都檢查過就可以得到答案

Code

網友解答

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] res = new int[spells.length];

        // Go through all the spells
        for (int i = 0; i < spells.length; ++i) {
            int spell = spells[i];
            int l = 0, r = potions.length - 1;
            
            // Binary search the success value
            while (l <= r) {
                int mid = l + (r - l) / 2;
                long tmp = (long) spell * (long) potions[mid];

                // Current num has satisfied the threshold
                if (tmp >= success) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            // Record the count of the pairs
            res[i] = potions.length - l;
        }
        return res;
    }
}