Q

給定N點與整數座標找到平行線的數量

2014-10-08 28 views 0 likes

0

nC2將給出我們可以在O（n^2）複雜度中形成的行數。
在O（n^2）複雜度中查找這些行的斜率並將它們存儲在數組中，比如x。
在O（n^2 logn）複雜度中排序x。
搜索O（n^2）時間內的平行線。

我們可以做得更好嗎？給定N點與整數座標找到平行線的數量

如果我必須找出是否有兩條線是平行的，那就是了。如果沒有找到所有的線，我們可以這樣做嗎？

2014-10-08 Amit Srivastava

+0

將其發佈在http://math.stackexchange.com/上。 – 2014-10-08 07:34:24

+0

您的符號有點誤導。實際上，1：O（N²）; 2：O（N 2）; 3：O（N²Log（N））; 4：O（N 2）。 – 2014-10-08 07:53:57

+0

是的。謝謝。 – 2014-10-08 07:56:57

A

回答

1

由於座標是整數，所以可以使用散列表來存儲N²斜率;將它們表示爲不可簡化的分數。這應該限制搜索等於O（N²）。

2014-10-08 08:05:59

+0

+1：我很確定這與3SUM問題處於相同的複雜性等級，所以這是您可以做的最好的部分。 – Nuclearman 2014-10-08 08:07:26

相關問題