LeetCode 筆記 - 2300. Successful Pairs of Spells and Potions

Posted on

題目在此 2300. Successful Pairs of Spells and Potions

給定兩個整數陣列 spells 和 potions，以及一個整數 success。對於每個 spells[i]，請找出有多少個 potions[j] 使得

$$spells[i] * potions[j] >= success$$

解題思維

每一個 spell 都需要找到可以成功的 potion 數量，所以我們可以先將 potions 排序，然後對每一個 spell 使用 binary search 找到最小的 potion，使得

$$
spell * potion >= success
$$

這樣我們就可以知道 current spell 可以成功的 potion 數量為

$$size_p - left$$

最後在幫計算過程中使用 @cache 儲存結果，避免重複計算即可。

Time complexity 是 $O(n \log n)$
其中 n 是 potions 的長度，因為我們需要對 potions 進行排序，然後對每個 spell 使用 binary search。

Space complexity 是 $O(n)$，因為我們需要儲存排序後的 potions。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:

        # step 0: sort the potions
        # step 1: use binary search to find the min p to success with cur spell, the num of success = size_p - left
        # step 2: count each result!

        # time complexity: O(n log n)
        # space complexity: O(n)

        potions.sort()

        size_p = len(potions)

        @cache
        def count_success(cur_spell):

            result = 0

            left = 0
            right = size_p - 1

            while left <= right:
                mid = left + (right - left) // 2

                if cur_spell * potions[mid] < success:
                    left = mid + 1
                else:
                    right = mid -1

            return size_p - left


        result = []

        for spell in spells:
            result.append(count_success(spell))

        return result

也許你也會想看看