问计算给定线的交点数量
EN

Stack Overflow用户

提问于 2013-04-14 15:16:25

回答 1查看 1.9K关注 0票数 2

我正在为谷歌的电话面试做准备，遇到了这个问题：

给定2D空间中的一列直线，如何在不到O(n^2)的时间内计算交叉点的数量？

他们说，面试官给出了一个O(n^2)的解决方案，然后面试官问他是否可以提出一个更好的解决方案。

谢谢。

回答已采纳

发布于 2013-04-14 15:25:55

二维中的两条直线要么相交一次，要么平行。如果没有平行的直线，则有n*(n-1)个/2交点。O(n log n)的解决方案是按斜率对线进行排序，然后扫描并行度，为找到的每组m条平行线减去m*(m-1)/2。

当然，这忽略了浮点舍入的任何实际问题，但我假设如果需要考虑这一点，问题中会提到这一点。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15996688

复制

相似问题

问计算给定线的交点数量EN