題目描述:給定咒語陣列 spells 和藥水陣列 potions,以及一個成功閾值 success。若 spells[i] * potions[j] >= success,則稱這對咒語與藥水「成功配對」。對每個咒語,求它能與多少瓶藥水成功配對。
解題思路:對每個咒語 s,能成功配對的藥水需滿足 potion >= ceil(success / s),即 potion >= (success + s - 1) / s(整數上取整)。先將 potions 排序,再對每個咒語以二分搜尋找到第一個滿足條件的藥水位置,從該位置到陣列末尾的所有藥水都能與該咒語配對。配對數量 = 陣列長度 - 該位置索引。使用 lower_bound 可直接找到第一個 ≥ 閾值的元素位置。
時間複雜度:O((n + m) log m) — 排序 potions 需 O(m log m);對每個咒語做一次二分搜尋需 O(log m),共 n 個咒語,合計 O(n log m);整體為 O((n + m) log m)。
空間複雜度:O(m) 或 O(1)(不計輸出) — 排序 potions 為原地操作,只需 O(1) 額外空間(或 O(m) 若計排序使用的遞迴堆疊)。輸出陣列不計入額外空間。
1. Sort potions array in ascending order 2. m = length of potions 3. For each spell s in spells: a. Compute minPotion = ceil(success / s) [integer: (success + s - 1) / s] b. Use lower_bound to find index idx of first potion >= minPotion c. count = m - idx d. Append count to result 4. Return result
方法一:暴力雙迴圈 — O(n * m)
對每個咒語,遍歷所有藥水,檢查 spell * potion >= success。當 n 和 m 各達到 10^5 時,10^10 次運算必然超時,僅適合理解題意。
方法二:排序雙指針 — O(n log n + m log m)
同時對 spells(保留原始索引)和 potions 排序,使用雙指針從最大咒語開始向下遍歷,指針只往前移動,整體線性掃描。時間複雜度相近但常數更小,實作稍複雜。此法在咒語也有序的情況下特別高效。
success 的值非常大(接近 10^10),乘積 spell * potion 可能溢出 32 位元整數,程式碼中應如何防止溢出?spells 陣列的順序,是否能設計出比現有方法更快的演算法?