Successful Pairs of Spells and Potions

題目描述

給定 spells 和 potions 兩個陣列，以及一個整數 success。當 spells[i] * potions[j] >= success 時為成功配對。回傳一個陣列，其中第 i 個元素是第 i 個法術的成功配對數。

輸入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
輸出：[4,0,3]
解釋：spell=5 配對 [2,3,4,5]→4個, spell=1 配對 0個, spell=3 配對 [3,4,5]→3個

解題思路

排序藥水

將 potions 升序排列，排序後相同強度的藥水聚在一起，便於二分搜尋

計算門檻

對每個 spell，最低需要的藥水強度 = ceil(success / spell)。例如 success=7, spell=3 → 門檻 = ceil(7/3) = 3

二分搜尋

在排序後的 potions 中用 bisect_left 找第一個 ≥ 門檻的位置 pos

計算配對數

pos 及其右邊的藥水都能成功配對，數量 = potions.length - pos

程式碼

C#

csharp

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        Array.Sort(potions);
        int n = potions.Length;
        int[] result = new int[spells.Length];
        
        for (int i = 0; i < spells.Length; i++) {
            // 最低需要的藥水強度
            long minPotion = (success + spells[i] - 1) / spells[i]; // ceil division
            // 二分搜尋第一個 >= minPotion 的位置
            int left = 0, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (potions[mid] >= minPotion) right = mid;
                else left = mid + 1;
            }
            result[i] = n - left;
        }
        return result;
    }
}

TypeScript

typescript

function successfulPairs(spells: number[], potions: number[], success: number): number[] {
    potions.sort((a, b) => a - b);
    const n = potions.length;
    
    return spells.map(spell => {
        const minPotion = Math.ceil(success / spell);
        // 二分搜尋第一個 >= minPotion 的位置
        let left = 0, right = n;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (potions[mid] >= minPotion) right = mid;
            else left = mid + 1;
        }
        return n - left;
    });
}

Python

python

import bisect
import math
 
def successfulPairs(spells: list[int], potions: list[int], success: int) -> list[int]:
    potions.sort()
    n = len(potions)
    result = []
    
    for spell in spells:
        min_potion = math.ceil(success / spell)
        # bisect_left 找第一個 >= min_potion 的位置
        idx = bisect.bisect_left(potions, min_potion)
        result.append(n - idx)
    
    return result

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O((m + n) log n) | O(1)（不計輸出） |

其中 m = spells 長度，n = potions 長度。

Time：排序 potions O(n log n) + 對每個 spell 做一次二分搜尋 O(log n)，共 m 個 spell，合計 O((m + n) log n)
Space：排序為 in-place，不計輸出的話是 O(1)（Python 的 sort 內部用 O(n)）

圖解

排序 potions

排序後→

遍歷每個 spell

ceil(success/spell)→

計算門檻值

在 potions 中找→

Binary Search 找位置

計算數量→

n - pos = 成功配對數

流程展示「排序 + 二分搜尋」的經典模式：一次排序 O(n log n)，然後對每個 spell 用 O(log n) 找到分界點。分界點右邊的所有藥水乘以 spell 都 ≥ success，直接用 n - pos 算出配對數。

進階觀點

💡面試追問

為什麼要用 ceil(success / spell) 而不是直接除？ 因為需要 spell × potion ≥ success，換算成 potion ≥ success / spell。整數除法會截斷小數（如 7/3=2），但 potion=2 時 3×2=6 不夠 7，所以必須向上取整到 3。整數 ceil 公式：(success + spell - 1) / spell。
如果 spells 也排序，能用雙指標優化嗎？ 可以。將 spells 降序排序後，spell 越小門檻越高，二分搜尋的起始位置只會右移。但需要額外的索引映射來還原原始順序，增加實作複雜度。
這題的核心模式是什麼？ 「排序 + 二分搜尋」——當需要對每個查詢計算「滿足條件的元素數量」時，先排序再二分是最典型的做法。

邊界情況

spell 極大導致門檻為 0 或 1：所有 potions 都能配對，二分搜尋返回位置 0，配對數 = n
spell 極小導致門檻超過 max(potions)：沒有任何 potion 能配對，二分搜尋返回 n，配對數 = 0
success 等於 1：只要 spell × potion ≥ 1，因為 spell 和 potion 都是正整數，所以所有配對都成功

理解測驗

🤔 為什麼先排序 potions 再用二分搜尋，而不是對每個 spell 暴力遍歷 potions？

🤔 如果某個 spell 非常大，使得所有 potions 都能成功配對，二分搜尋會返回什麼位置？