l*******r
发帖数: 511 | 1 2-D plane,有6k个点，要求出一条直线，使之过的点最多，怎么做呢？我只能想到O（N
^2）
的解法。。 |
r**u
发帖数: 1567 | 2 说说怎么做到O(n^2)吧，我只想到n^3的。
（N
【在 l*******r 的大作中提到】
: 2-D plane,有6k个点，要求出一条直线，使之过的点最多，怎么做呢？我只能想到O（N
: ^2）
: 的解法。。
|
s*****i
发帖数: 355 | 3 我只能到 O(n^2*logn)
【在 r**u 的大作中提到】
: 说说怎么做到O(n^2)吧，我只想到n^3的。
:
: （N
|
P*******e
发帖数: 1353 | 4 pair-wise算斜率,按照斜率分组，然后看每个组里面的connection degree?
【在 r**u 的大作中提到】
: 说说怎么做到O(n^2)吧，我只想到n^3的。
:
: （N
|
g*******y
发帖数: 1930 | 5 严格的来说，我也只能想到 nnlogn的
【在 s*****i 的大作中提到】
: 我只能到 O(n^2*logn)
|
s*****i
发帖数: 355 | 6 每两个点算斜率和截距，然后一起做为key加到hashtable里面，value是计数器
这样是不是O(n^2)?
【在 g*******y 的大作中提到】
: 严格的来说，我也只能想到 nnlogn的
|
g*******y
发帖数: 1930 | 7 浮点数用hash会有问题
【在 s*****i 的大作中提到】
: 每两个点算斜率和截距，然后一起做为key加到hashtable里面，value是计数器
: 这样是不是O(n^2)?
|
t*********n
发帖数: 1292 | |
H*M
发帖数: 1268 | 9 斜率和洁具一般是double吧，怎么能作为key?
【在 s*****i 的大作中提到】
: 每两个点算斜率和截距，然后一起做为key加到hashtable里面，value是计数器
: 这样是不是O(n^2)?
|
s*****i
发帖数: 355 | 10 是啊，但是我想不出来更好的了。要是面试再追问我，也就只能这么答了.最多说把分
子分母分开保存，不用浮点数呗。多算一次求斜率和截距分子分母的GCD
【在 g*******y 的大作中提到】
: 浮点数用hash会有问题
|
|
|
s*****i
发帖数: 355 | 11 要严格来说，nnlogn的排序，也一样不能直接用浮点数排序吧。差一点点那个点就不是
一条直线了，哈哈
【在 s*****i 的大作中提到】
: 是啊，但是我想不出来更好的了。要是面试再追问我，也就只能这么答了.最多说把分
: 子分母分开保存，不用浮点数呗。多算一次求斜率和截距分子分母的GCD
|
g*******y
发帖数: 1930 | 12 如果要求在同一直线上，是严格的同一直线，那么你这个方法不错。
我理解的是，同一直线的判定，有一个的精度范围，这样就没法用hash了。
【在 s*****i 的大作中提到】
: 是啊，但是我想不出来更好的了。要是面试再追问我，也就只能这么答了.最多说把分
: 子分母分开保存，不用浮点数呗。多算一次求斜率和截距分子分母的GCD
|
s*****i
发帖数: 355 | |
i**********b
发帖数: 77 | |
s*****i
发帖数: 355 | |
i******t
发帖数: 370 | 16 I was wrong...Looks like hashtable is the best.
【在 s*****i 的大作中提到】
: 没看懂
:
: once.
|
