gpt4 book ai didi

algorithm - 寻找一种有效的算法来获得一条线

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:39:09 24 4
gpt4 key购买 nike

给定 n 个水平线段,其中每个线段的范围是 x2 - x1,我应该应用什么算法来获得一条直线,使我获得最大的组合范围(与线段的每个交叉点添加该段的范围),这就像找到一条线来钻孔,以获得最大的水量(水代表具有 X2-X1 数量的段)我用一个郁闷的大O(n^4)

完成了蛮力算法

最佳答案

我假设没有段从另一个段开始,如果没有则需要修改以下内容:

  • 为每个段创建 2 个元组:(x1, index) 和 (x2, index)
  • 按第一个值对元组排序
  • 设置最佳 = 0
  • 迭代元组。如果它是起点(以前没有看到索引),请将其值 (x2 - x1) 添加到 best。如果它是终点,则将其值减去最佳值。
  • 问题的答案将是最好达到的最高值。

复杂度:O(n log n)

关于algorithm - 寻找一种有效的算法来获得一条线,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53698618/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com