二分查找算法的应用——LeetCode1011

本文共621个字,预计阅读时间需要2分钟。

二分查找又称折半查找,它是一种效率较高的查找方法。

原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前 面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。

LeetCode 1011

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1:

示例 2:

示例 3:

 

提示:

  1. 1 <= D <= weights.length <= 50000
  2. 1 <= weights[i] <= 500

思路

  • 结果一定落在max(weights)到sum(weights)之间
  • 左端点对应每天一条船,但是会导致超出D天
  • 右端点对应1天有一条大船,不能满足最小的载货量
  • 利用二分法(二分值便是当前的ans),每一次模拟运货根据当前需要总天数与D不断二分,逼近最终的结果

详解代码

结果

读者评分
[评分人数: 0 平均分: 0]

1 位极客 “二分查找算法的应用——LeetCode1011

评论

OmegaXYZ