gpt4 book ai didi

algorithm - 统计两组序列的交点(线)

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

我必须找到一种算法,可以找到两组数组之间的交集总数,而其中一个数组已排序。

举个例子,我们有这两个数组,我们向相应的数字画直线。 Intersection Points

这两个数组为我们提供了总共 7 个交集

有什么样的算法可以帮助我解决这个问题?

我使用了搜索按钮,但没有找到任何可以为我解决这个问题的东西。

谢谢

最佳答案

给定两个数 M 和 N,如果

  • 顶部M在顶部N的右边,底部M在底部N的右边
  • 顶部M在顶部N的左边,底部M在底部N的左边

另外两种情况:

  • 左上右下
  • 右上,左下

这些线确实相交。

在示例中,8 在顶行所有 4 个数字的左侧,在底部 3 个数字的右侧,因此 8 与三个数字相交。

5 在上面 8 的右边,在下面 8 的左边,给出一个交点。 5 在顶部的 4 和 1 的左侧,在底部的 4 和 1 的右侧,再给出两个。所以 5 与三个数字相交。

请注意,我们计算了 5 和 8 的交集两次。事实上,每个路口都会被计算两次。如果完成该示例,您将计算出 14 个交叉点。最后除以 2 得到答案。

关于algorithm - 统计两组序列的交点(线),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41084239/

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