Re: [閒聊] 每日LeetCode

作者: yueayase (scrya)   2023-04-03 02:26:08
※ 引述《Rushia (みけねこ的鼻屎)》之銘言:
: 2300. Successful Pairs of Spells and Potions
: 給定兩個陣列spells和points,前者表示多個咒語的強度,後者表示多個藥劑的強度,若
: 咒語和藥劑相乘大於success則這一組咒語和藥劑配對成功,返回一個長度為spells的陣列
: pairs,其中 pairs[i] 是能與第 i 個咒語配對成功的藥劑數量。
: Example:
: Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
: Output: [4,0,3]
: Explanation:
: - 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
: - 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
: - 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
: Thus, [4,0,3] is returned.
: 思路:
: 1.最簡單的方法就是兩個陣列相互配對並計算數量,但是咒語和藥劑的長度很大這樣做
: 肯定會吃TLE。
: 2.我們可以先把藥劑的強度排序好,每個咒語使用二分搜索找到最小且滿足success的
: 藥劑,這樣這個索引的右邊全部都是配對成功的藥劑,若potions.length = n
: 滿足數量就會是 n - index,如果最右邊(最大)的藥劑和咒語不滿足則二分搜索直接
: 返回n不用繼續找尋。
: Java Code:
:
作者: pandix (麵包屌)   2023-04-03 02:33:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com