2300. Successful Pairs of Spells and Potions

題目

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

題目連結

思路

這題主要的核心圍繞在矩陣的操作，將 spells 的每個數字乘到 potions 裡面再和 success 進行比較就可以得到成功的 pairs 數量，可以寫成下面的樣子：

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        pairs = []

        for spell in spells:
            products = list(map(lambda x: x * spell, potions))
            pairs.append(len(list(filter(lambda x: x >= success, products))))

        return pairs

雖然題目本身的邏輯並不複雜，不過如果直接照著邏輯去寫的話在測資時會撞到 Time Limit Exceeded 的錯誤，所以需要找到更有效率的算法來減少複雜度。

由於目標是找到相乘的結果超過門檻即可，因此可以先將 potions 進行排序，利用 binary search 找到能夠通過的最低強度，就不需要把整個陣列的跑過計算一遍。

和一般的二分搜尋不同的地方在於，此題要找到並不是指定的元素，而是找到結束時的 index，以下面的例子來說，結束搜尋時所停留的 index 應該分別是 1, 4, 2。

spells = [5, 1, 3]
potions = [1, 2, 3, 4, 5]
success = 7
5 * potions = [5, 10, 15, 20, 25] -> 4
1 * potions = [1, 2, 3, 4, 5] -> 0
3 * potions = [3, 6, 9, 12, 15] -> 3
=> [4, 0, 3]

其中關鍵的差異在於結束的那回合是上界往下移還是下界往上移導致觸發結束條件下界>上界，會影響最後要回傳的 index 是否要 +1，因此加入了一個 bool 來確認這件事情，如果是從上界往下移導致結束的話就維持原本的 index，否則就需要把 index + 1 再回傳出來。

最後再用 potions 的長度去扣即可得到符合條件的數量。

Full Code

class Solution:
    def binarySearch(self, nums, c, target):
        lower = 0
        upper = len(nums) - 1
        fromUpper = False

        while lower <= upper:
            mid = (lower + upper) // 2
            if c * nums[mid] >= target:
                upper = mid - 1
                fromUpper = True
            elif c * nums[mid] < target:
                lower = mid + 1
                fromUpper = False

        return mid if fromUpper else mid + 1

    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        pairs = []
        potions.sort()

        for spell in spells:
            goal = self.binarySearch(potions, spell, success)
            pairs.append(len(potions) - goal)
                
        return pairs