3

我在CareerCup上找到了一个 Google 面试问题

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

那里的许多答案说这个问题很难并且涉及某种特殊算法。

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

这是我的想法：

首先，我将为 2D 平面提供一个轴系。因此，每个点都有其唯一的 x 和 y，即{x, y}。为简单起见，我们可以将轴系{0, 0}作为整个平面的左下角，因此每个 x 和 y 都大于 0。

然后我有一个理论：

如果几个点在同一条线上，那么它必须是以下三种情况之一：

  1. 它们的x值相同
  2. 它们的y值相同
  3. 它们的x/y或y/x值相同。但是x/ycase 和 case 是一样的y/x，所以我们只关注x/y.

然后我将有 3 个哈希表。

  1. 第一个 ( hashtable-x) 是 key of x，value 是相同点的列表x；

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

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

然后我扫描整个 6000 个点，对于每个点，我将得到它的xfrom hashtable-x，并将该点放入该插槽的值（列表）中；hashtable-y然后我会对and做类似的事情hashtable-x-y。

最后，我将扫描 3 个哈希表中的所有列表，并找到最长的列表将包含所需行的点。

你觉得我的算法怎么样？

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

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

4

2 回答 2

2

您的算法将无法按说明工作。考虑许多点落在 y=2x + 1 线上，这意味着您得到 (1,3)、(2,5)、(3,7)、(4,9) 和 (5,11)。

我不认为你应该解决这个问题，除非你有计算几何的研究生课程。处理是将所有点转换为对偶空间中的线，使用点线对偶性并找到大多数线相交的点。天真地，您可以通过遍历每对线并以分析形式评估它们相交的位置，在 O(n^2) 中做到这一点。我还认为您可以通过使用平面扫描样式算法来完成 O(n log n)，但我不确定细节。

于 2012-06-07T14:34:43.350 回答
0

我将假设我的答案中的点数大于或等于 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)
于 2012-06-07T15:14:01.587 回答