寻找穿过最多点的直线

Question

我在CareerCup上找到了一道谷歌面试题。

给定一个二维平面，假设其上有大约6000个点。找到一条穿过最多点的直线。

许多答案都说这个问题很难，需要使用某些特殊算法。

但是我的观点不同，也许我是错的。

以下是我的想法：

首先我会为二维平面建立坐标系。因此，每个点都有其唯一的x和y，即{x, y}。为了简单起见，我们可以将坐标系的{0, 0}放在整个平面的左下角，因此每个x和y都大于0。

然后我有一个理论：

如果几个点在同一条直线上，则必须符合以下3种情况之一：

1. 它们的x值相同
2. 它们的y值相同
3. 它们的x/y或y/x值相同。但是x/y情况与y/x情况相同，因此让我们只关注x/y。

然后我将有3个哈希表。

1. 第一个（hashtable-x）的键为x，值是具有相同x的点的列表；

2. 第二个（hashtable-y）的键为y，值是具有相同y的点的列表；

3. 最后一个（hashtable-x-y）的键为x/y，值是具有相同x/y的点的列表；

然后我扫描整个6000个点，对于每个点，我将从hashtable-x中获取其x，并将该点放入该插槽的值（列表）中；然后我将对hashtable-y和hashtable-x-y执行类似的操作。最后，我将扫描3个hashtable中的所有列表，并找到包含所需线条的点的最长列表。您认为我的算法怎么样？

---

好的，这里是重复的问题，很抱歉我之前没有找到这个问题。

什么是通过最多点的直线的最有效算法？

- Jackson Tale

---

考虑到 x/y 比率只会考虑起点为 {0, 0} 的线。想象所有的点都在直线上，其中 y = x + 1，它们都有另一个 x，另一个 y 和另一个 x/y。 - Nobody moving away from SE

@Nobody 是的，你说得对。我需要更深入地思考这个问题。 - Jackson Tale

Answer 1

你的算法无法按照所述工作。考虑到很多点都在直线y=2x+1上，这意味着你得到了(1,3)、(2,5)、(3,7)、(4,9)和(5,11)。

我认为除非你拥有计算几何方面的研究生课程，否则你不应该被要求解决这个问题。解决方案是使用点线对偶将所有点转换为对偶空间中的线，并找到大多数线相交的点。朴素地说，你可以通过遍历每对线并评估它们在解析形式下相交的位置来以O(n^2)的时间复杂度进行这个操作。我也认为你可以使用平面扫描样式的算法以O(n log n)的时间复杂度进行，但我不确定细节上的问题。

- carlosdc

---

谢谢。将所有点转换为对偶空间中的线是什么意思？如何准确地执行它？ - Jackson Tale

对于每个点（x，y），你可以说y = ax + b。解出b = -xa + y，这就是在对偶A-B空间中的一条直线。对于每个点都这样做，并相交线条。 - carlosdc

你是指一条线的形式是 y = ax+b ，其中 a 和 b 是已知的吗？@tskuzzy 的回答怎么样？ - Jackson Tale

不，b = -xa + y，其中x和y是已知的，这是a-b轴上的一条直线。他的解决方案是O(n^3)的解决方案，对于6000个点来说是不切实际的。 - carlosdc

@carlosdc：现在我认为对于6000个元素，原则上不应该认为O(N^3)的解决方案是不切实际的。循环2e11次可能只需要几分钟。 - salva

Answer 2

我假设这里的点数大于或等于2（零和一个点是微不足道的情况）。

首先注意到任何这样的直线必须通过至少两个点。因此，我们可以按照以下方式构建解决方案：

for each pair of points p1,p2
    find equation of the line l passing through p1,p2

    for each point p3 not p1 or p2
        if p3 lies on l
            counter[l]++

return argmax(counter)

- tskuzzy

---

这是一种O(N^3)的方法，对吧？ - Jackson Tale

选择每一对的时间复杂度接近O(n^2)（技术上是nCr的长度），并且对于每一对，我们都要与所有其他项进行比较（O(n)），因此我认为它的时间复杂度是O(N^3)。 - everlasto