LeetCode算法题(Go语言实现)_54

题目

给你两个正整数数组 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] = 0
			continue
		}
		s64 := int64(s)
		minPotion := (success + s64 - 1) / s64
		idx := sort.Search(m, func(j int) bool {
			return int64(potions[j]) >= minPotion
		})
		res[i] = m - idx
	}

	return res
}

二、算法分析

1. 核心思路

• 排序与二分查找：通过将药水数组排序，对每个咒语使用二分查找快速确定满足条件的最小药水位置。
• 数学优化：利用整数运算避免浮点计算，准确计算每个咒语所需药水的最小值。

2. 关键步骤

1. 预处理药水数组：对药水数组进行排序以便后续二分查找。
2. 遍历咒语数组：对每个咒语计算所需药水的最小值。
3. 二分查找确定位置：使用二分查找确定第一个满足条件的药水位置，从而计算出满足条件的药水数量。

3. 复杂度

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 咒语强度极大：当咒语强度极大时，所需药水值极小，可能全部满足。
• 药水全不满足：当药水最大值仍小于最小需求时，结果为0。
• 成功值为0：根据题意成功值始终为正，无需处理。

2. 扩展应用

• 多维匹配：扩展到多维属性匹配问题（如多条件组合）。
• 动态药水更新：支持动态添加/删除药水并实时查询。
• 分布式处理：大规模数据时采用分布式排序与查询。

3. 多语言实现

import bisect

def 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. 扩展方向

• 动态阈值调整：支持动态变化的成功阈值。
• 多条件组合：结合多个条件（如药水类型、等级）进行匹配。
• 实时反馈系统：集成到实时游戏系统中进行高效匹配计算。