algorithm - 计算相交点需要多少条直线的最快方法？

Question

我正在进行编码面试，尽管我能够解决它，但我的表现得分很低，我认为我需要改进。

问题:

输入是图形上的点数组。例如 [(-1, -2), (1, 2), (2, 4), (2, 3)]

从点(0, 0)开始，需要画多少条直线才能与所有点相交？

解决方案:

我在 O(n) 中解决了这个问题，方法是遍历所有点并将比率存储在一个集合中，然后返回集合中的项目数。因此，例如 (1, 2) 和 (2, 4) 具有相同的比率，因此一条线可以穿过它们。

你如何以比 O(n) 更快的方式解决这个问题？

我的代码:

def countRays(points):
  positiveRatios = set()
  negativeRatios = set()
  for point in points:
    x, y = point
    if x < 0 or y < 0:
      symbol = "-"
    else:
      symbol = "+"

    ratios = positiveRatios if x >= 0 else negativeRatios
    if x == 0:
      ratios.add( (symbol, 1,) )
    else:
      ratios.add( (symbol, y/x,) )
  return len(positiveRatios) + len(negativeRatios)

Answer 1

这不能比 O(n) 更快地解决。每个点都可以产生一条新线，因此您必须至少查看每个点一次。