Medium

题目描述

给你两个正整数数组 spells 和 potions，长度分别为 n 和 m，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 个药水的能量强度。

同时给你一个整数 success。一个咒语和药水的能量强度乘积如果大于等于 success，那么它们就能组成一个成功的对数。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能够与第 i 个咒语成功组成对数的药水数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25]。4 对成功。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5]。0 对成功。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15]。3 对成功。
因此，[4,0,3] 被返回。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24]。2 对成功。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8]。0 对成功。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16]。2 对成功。
因此，[2,0,2] 被返回。

提示：

  • n == spells.length
  • m == potions.length
  • 1 <= n, m <= 10^5
  • 1 <= spells[i], potions[i] <= 10^5
  • 1 <= success <= 10^10

解题思路

这道题要求找到每个咒语能与多少个药水成功配对。核心观察是：如果一个咒语与某个药水能成功配对，那么它与所有更强的药水也能成功配对。

思路分析：

  1. 暴力解法：对每个咒语，遍历所有药水计算乘积。时间复杂度为 O(n×m)，会超时。

  2. 排序 + 二分查找（推荐）：

    • 首先将药水数组排序
    • 对于每个咒语 spells[i]，需要找到满足 spells[i] × potions[j] >= success 的最小药水强度
    • 即找到 potions[j] >= success / spells[i] 的最小位置
    • 使用二分查找快速定位这个位置，剩余的所有药水都能成功配对

关键点：

  • 使用 (success + spells[i] - 1) / spells[i] 进行向上取整，避免浮点数精度问题
  • 二分查找找到第一个大于等于目标值的位置
  • 成功配对数 = 总药水数 - 找到的位置索引

这种方法时间复杂度为 O(m log m + n log m)，空间复杂度为 O(1)（不计算结果数组）。

代码实现

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> result;
        
        for (int spell : spells) {
            long long minPotion = (success + spell - 1) / spell; // 向上取整
            int index = lower_bound(potions.begin(), potions.end(), minPotion) - potions.begin();
            result.push_back(potions.size() - index);
        }
        
        return result;
    }
};

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        result = []
        
        for spell in spells:
            min_potion = (success + spell - 1) // spell  # 向上取整
            index = bisect.bisect_left(potions, min_potion)
            result.append(len(potions) - index)
        
        return result

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        Array.Sort(potions);
        int[] result = new int[spells.Length];
        
        for (int i = 0; i < spells.Length; i++) {
            long minPotion = (success + spells[i] - 1) / spells[i]; // 向上取整
            int index = Array.BinarySearch(potions, (int)Math.Min(minPotion, int.MaxValue));
            if (index < 0) index = ~index; // 如果没找到，转换为插入位置
            result[i] = potions.Length - index;
        }
        
        return result;
    }
}

var successfulPairs = function(spells, potions, success) {
    potions.sort((a, b) => a - b);
    const result = [];
    
    for (const spell of spells) {
        const minPotion = Math.ceil(success / spell);
        let left = 0, right = potions.length;
        
        // 二分查找第一个 >= minPotion 的位置
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (potions[mid] >= minPotion) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        result.push(potions.length - left);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
排序 + 二分查找O(m log m + n log m)O(1)

其中 n 是咒语数组长度，m 是药水数组长度。排序需要 O(m log m)，每个咒语进行二分查找需要 O(log m)，总共 n 次查找。

相关题目