給定
spells和potions兩個陣列以及一個整數success。當spells[i] * potions[j] >= success時為成功配對。回傳每個 spell 的成功配對數量。
Example:
Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7 Output: [4,0,3]
Intuition
TIP
排序 potions 後，對每個 spell 二分搜尋找到最小的 potion 使乘積 >= success。
- 對每個 spell，需要找
potion >= ceil(success / spell)的數量 - 先排序 potions，再用二分搜尋找 lower bound
Approaches
1. Brute Force — O(m * n) / O(m)
- Idea: 對每個 spell，遍歷所有 potions 計算成功配對數
- Time:
O(m * n)（m = spells 長度，n = potions 長度） - Space:
O(m)（結果陣列）
Brute Force Code
class Solution {
fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
return IntArray(spells.size) { i ->
potions.count { p -> spells[i].toLong() * p >= success }
}
}
}⭐ 2. Sort + Binary Search — O((m + n) * log n) / O(m)
- Idea: 排序 potions，對每個 spell 二分搜尋第一個使乘積 >= success 的 potion 位置
- Time:
O((m + n) * log n) - Space:
O(m)（結果陣列，不計排序空間）
class Solution {
fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
potions.sort()
val n = potions.size
return IntArray(spells.size) { i ->
val spell = spells[i].toLong()
// 找第一個 potion 使得 spell * potion >= success
var left = 0
var right = n
while (left < right) {
val mid = left + (right - left) / 2
if (spell * potions[mid] >= success) {
right = mid
} else {
left = mid + 1
}
}
n - left // left 之後的所有 potion 都可以成功配對
}
}
}WARNING
注意使用 Long 避免 spell * potion 溢位。n - left 就是從 left 位置到末尾的元素個數，即成功配對數。
🔑 Takeaways
- Pattern: 排序 + 二分搜尋（Lower Bound）
- Key trick: 先排序其中一個陣列，再對另一個陣列的每個元素做二分搜尋。找到分界點後，用陣列長度減去索引即為符合條件的數量