LeetCode 筆記 - 2300. Successful Pairs of Spells and Potions
題目在此 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 | class Solution: |