当前位置:   article > 正文

【限时免费】20天拿下华为OD笔试之【二分查找】2023B-最佳植树距离【欧弟算法】全网注释最详细分类最全的华为OD真题题解_od 最佳种植距离

od 最佳种植距离

二分查找】2023B-最佳植树距离

题目描述与示例

题目描述

小明在直线的公路上种树,现在给定可以种树的坑位的数量和位置,以及需要种多少棵树苗,问树苗之间的最小间距是多少时,可以保证种的最均匀(两棵树苗之间的最小间距最大)

输入

输入三行:

  • 第一行一个整数:坑位的数量
  • 第二行以空格分隔的数组:坑位的位置
  • 第三行一个整数:需要种植树苗的数量

输出

树苗之间的最小间距

示例一

输入

7
1 3 6 7 8 11 13
3
  • 1
  • 2
  • 3

输出

6
  • 1

说明

三颗树苗分别种在 1713 的位置,可以保证种的最均匀,树苗之间的最小间距为 6。如果选择最小间距为 7,则无法种下3颗树苗。

解题思路

二段性分析

考虑最小种植间距interval可种植树木数量之间的关系

  • 最小种植间距interval越大的时候,在原列表trees中只能种下越少的树。当取到最值interval = max(trees) - min(trees)时,则只能种下一棵树,可种植树木数量为1
  • 最小种植间距interval越小的时候,在原列表trees中可以种下越多的树。当取到最值interval = 1时,所有坑位都能种下树木,可种植树木数量为len(trees)
  • 对于在区间[1, max(trees) - min(trees)]之间取值的最小种植间距interval而言,一定存在一个值ans,使得
    • interval ∈ [0, ans]时,可以种下N棵树。
    • interval ∈ (ans, max(bucketBallNums)]时,不能种下N棵树。
    • 这体现了这个问题的二段性ans是我们需要的答案,而ans的寻找就可以用二分查找来完成。

子问题分析

对于二分查找过程中得到的每一个最小种植间距interval = mid,我们都要去判断在该间距的条件下 trees 数组能否成功种下 N 棵树。对于这个问题,我们可以用贪心的思路来解决

  • 我们需要先对trees数组以升序排序,这样才能方便统计相邻坑位距离
  • 我们已知前一棵树的位置是pre_tree,那么对于当前树位置cur_tree,当
    • 当前树 cur_tree 和上一棵树 pre_tree 的距离大于等于最小种植间距interval,我们种下当前树,种下树的总数 num增加1。同时,对于后面的树而言,当前树 cur_tree 成了其上一棵树,故修改上一棵树的变量pre_tree = cur_tree
    • 当前树 cur_tree 和上一棵树 pre_tree 的距离小于最小种植间距interval,无法种下当前树,pre_tree也无需做出任何修改。
  • 由于第一个位置肯定贪心地被种下,因此种下的数目num初始化为1,同时初始化pre_tree = trees[0]即为第一棵树的位置。

上述逻辑整理为代码即构建 check_available(interval, trees, N) 函数

def check_available(interval, trees, N):
    num = 1
    pre_tree = trees[0]
    for cur_tree in trees[1:]:
        if cur_tree - pre_tree >= interval:
            pre_tree = cur_tree
            num += 1
            if num == N:
                return True
    return False
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

代码

# 题目:2023B-最佳植树距离
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:二分查找
# 代码看不懂的地方,请直接在群上提问


# 该函数用于检查:当选择两树最小间距为 interval 时,能否种下 N 棵树
def check_available(interval, trees, N):
    # 第一个位置肯定种下,因此种下的数目num初始化为1
    num = 1
    # 初始化变量 pre_tree,用于记录上一棵树的位置
    pre_tree = trees[0]
    # 从索引为1的树开始,遍历所有trees
    for cur_tree in trees[1:]:
        # 如果当前树 cur_tree 和上一棵树 pre_tree 的距离超过传入的间距 interval,
        # 那么可以在cur_tree的位置种下一棵树,故种下的数目+1
        # 同时 pre_tree 需要更新为 cur_tree,即对于下一棵树而言,当前cur_tree是其上一棵树
        if cur_tree - pre_tree >= interval:
            pre_tree = cur_tree
            num += 1
            # 如果在当前interval的条件下,当前种下数目 num 可以等于要求种植数量 N,
            # 那么返回 True,表示该 interval 是一个合适的间隔距离。
            if num == N:
                return True
    return False


# M个坑
M = int(input())
# M个坑位具体位置
trees = list(map(int, input().split()))
# 种N棵树
N = int(input())

# 对trees数组进行排序,方便统计相邻坑位距离
trees.sort()

left, right = 1, trees[-1] - trees[0] + 1

# 左闭右开区间,退出循环时存在 left = right = mid
# 循环不变量为left < right
while left < right:
    # 计算 left 和 right 的平均值 mid
    mid = (left + right) // 2
    # 当间隔取 mid 时,可以种入 N 棵树
    # 说明当前间隔 mid 太小,left右移
    # 退出循环时,left 恰好不满足if条件语句
    # 即存在 check_available(left, trees, N)为False
    # left是该式子成立的第一个整数,故 left - 1是为答案
    if check_available(mid, trees, N):
        left = mid + 1
    else:
        right = mid

# interval = left-1 是使得
# check_available(interval, trees, N)满足的最大整数
print(left - 1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

时空复杂度

时间复杂度O(MlogN + MlogM)

  • 排序时间复杂度为O(MlogM)
  • 子问题单次求解即函数check_available(interval, trees, N)时间复杂度为O(M)
  • 二分查找算法的时间复杂度为O(logN)。每次都需要调用check_available()函数,故总的二分查找时间复杂度度为O(MlogN)

空间复杂度:O(1)

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,200+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/607229
推荐阅读
相关标签
  

闽ICP备14008679号