題目
給你兩個正整數數組 spells 和 potions ，長度分別為 n 和 m ，其中 spells[i] 表示第 i 個咒語的能量強度，potions[j] 表示第 j 瓶藥水的能量強度。
同時給你一個整數 success 。一個咒語和藥水的能量強度 相乘 如果 大于等于 success ，那么它們視為一對 成功 的組合。
請你返回一個長度為 n 的整數數組 pairs，其中 pairs[i] 是能跟第 i 個咒語成功組合的 藥水 數目。
一、代碼實現（Go語言實現）
import ("sort"
)func successfulPairs(spells []int, potions []int, success int64) []int {sort.Ints(potions)m := len(potions)res := make([]int, len(spells))for i, s := range spells {if s == 0 {res[i] = 0continue}s64 := int64(s)minPotion := (success + s64 - 1) / s64idx := sort.Search(m, func(j int) bool {return int64(potions[j]) >= minPotion})res[i] = m - idx}return res
}
二、算法分析
1. 核心思路
- 排序與二分查找：通過將藥水數組排序，對每個咒語使用二分查找快速確定滿足條件的最小藥水位置。
- 數學優化：利用整數運算避免浮點計算，準確計算每個咒語所需藥水的最小值。
2. 關鍵步驟
- 預處理藥水數組：對藥水數組進行排序以便后續二分查找。
- 遍歷咒語數組：對每個咒語計算所需藥水的最小值。
- 二分查找確定位置：使用二分查找確定第一個滿足條件的藥水位置，從而計算出滿足條件的藥水數量。
3. 復雜度
| 指標 | 值 | 說明 |
|---|---|---|
| 時間復雜度 | O(m log m + n log m) | 排序藥水數組耗時 O(m log m)，每個咒語二分查找耗時 O(log m) |
| 空間復雜度 | O(m) | 存儲排序后的藥水數組 |
三、圖解示例
四、邊界條件與擴展
1. 特殊場景驗證
- 咒語強度極大：當咒語強度極大時，所需藥水值極小，可能全部滿足。
- 藥水全不滿足：當藥水最大值仍小于最小需求時，結果為0。
- 成功值為0：根據題意成功值始終為正，無需處理。
2. 擴展應用
- 多維匹配：擴展到多維屬性匹配問題（如多條件組合）。
- 動態藥水更新：支持動態添加/刪除藥水并實時查詢。
- 分布式處理：大規模數據時采用分布式排序與查詢。
3. 多語言實現
import bisectdef successfulPairs(spells, potions, success):potions.sort()m = len(potions)return [m - bisect.bisect_left(potions, (success + s - 1) // s) for s in spells]
import java.util.Arrays;public class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {Arrays.sort(potions);int[] res = new int[spells.length];for (int i = 0; i < spells.length; i++) {int s = spells[i];long minPotion = (success + s - 1) / s;int idx = Arrays.binarySearch(potions, (int) minPotion);if (idx < 0) idx = -idx - 1;res[i] = potions.length - idx;}return res;}
}
五、總結與優化
1. 算法對比
| 方法 | 優勢 | 適用場景 |
|---|---|---|
| 二分查找 | 時間效率高 | 靜態數據查詢 |
| 線性掃描 | 無需預處理 | 小規模數據 |
| 哈希預處理 | 快速查詢 | 頻繁重復查詢 |
2. 工程優化
- 預處理緩存：對藥水數組預排序并緩存結果。
- 并行處理：多線程處理不同咒語的查詢。
- 內存優化：對排序后的藥水數組進行壓縮存儲。
3. 擴展方向
- 動態閾值調整：支持動態變化的成功閾值。
- 多條件組合：結合多個條件（如藥水類型、等級）進行匹配。
- 實時反饋系統：集成到實時游戲系統中進行高效匹配計算。
