【LeetCode】每日一题 2023_11_10 咒语和药水的成功对数（练习二分）

本文主要是介绍【LeetCode】每日一题 2023_11_10 咒语和药水的成功对数（练习二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刷题前唠嗑

LeetCode? 启动！！！

可恶，今天的题目怎么也这么长

题目：咒语和药水的成功对数

题目链接：2300. 咒语和药水的成功对数

题目描述

代码与解题思路

看完题目，怎么感觉怪怪的，先抛掉脑子吧~

暴力，启动！

func successfulPairs(spells []int, potions []int, success int64) (ans []int) {for _, v := range spells {cnt := 0for _, v2 := range potions {sum := int64(v)*int64(v2)if sum >= success {cnt++}}ans = append(ans, cnt)}return ans
}

启动失败。。。

是了，中等题怎么可能会让我们随便一个暴力就能过去呢。。。

菜鸟决定去看看题解是怎么做的，没啥思路

偷看大佬题解

二…二分？

这咋二分？这，这，还有这种操作，学会了

func successfulPairs(spells []int, potions []int, success int64) (ans []int) {sort.Ints(potions)for _, v := range spells {left, right := 0, len(potions)-1for left < right { // 二分找出成功组合的最小下标mid := left+(right-left)/2sum := int64(v)*int64(potions[mid])if sum >= success {right = mid} else {left = mid+1}}cmp := int64(v)*int64(potions[left])if cmp >= success {ans = append(ans, len(potions)-right)} else { // 没有一个组合成功ans = append(ans, 0)}}return ans
}

这道题可以用排序+二分查找的来做，我的主要算法流程如下：

1. 排序 potions 数组
2. 遍历 spells 数组
3. 通过二分查找，找出排序后的 potions 数组中能与 spellls 数组的数成组合的最小下标，举个例子：
   假设这时的 splles 中的元素是 3，sucess 是 9，potions 数组是 [1, 2, 3, 4, 5, 6]，二分之后得出的 right 就是 3，因为 3*3 以及乘之后的数 >= sucess 的数，符合题目要求
4. 然后用 len(potions)-right 就能得出能成功组合的数量了

这道题目使用二分降低时间复杂度的核心就是通过 logn 的算法，求出能够组合成功的数量，将 n 方的算法优化成了 nlogn 级别。

结语

今天早上睡了个懒觉，写的有点晚了，今天的每日一题就当是练习二分啦~

这篇关于【LeetCode】每日一题 2023_11_10 咒语和药水的成功对数（练习二分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---