z**********g
发帖数: 209 | 1 Given a two dimensional graph with 6000 points on it, find a line which
passes the most number of points。
谢谢了。 |
l*******r
发帖数: 511 | 2 hashtable, n^2..
【在 z**********g 的大作中提到】
: Given a two dimensional graph with 6000 points on it, find a line which
: passes the most number of points。
: 谢谢了。
|
r****o
发帖数: 1950 | 3 what is the key and value of hashtable?
【在 l*******r 的大作中提到】
: hashtable, n^2..
|
m*****g
发帖数: 226 | 4 好像据说for each point, calculate and hash the angle of any other point.
count the max on the same angle.
so O(n2) |
r****o
发帖数: 1950 | 5 how do you define the angle? slope? it is float.
【在 m*****g 的大作中提到】
: 好像据说for each point, calculate and hash the angle of any other point.
: count the max on the same angle.
: so O(n2)
|
a***9
发帖数: 364 | 6 这题好像本版见过。
就是对每两个点算slope和intersect,然后sort.
如果允许误差就直接把float sort,否则用分数表示。。
【在 z**********g 的大作中提到】
: Given a two dimensional graph with 6000 points on it, find a line which
: passes the most number of points。
: 谢谢了。
|
r****o
发帖数: 1950 | 7 请问sort是对slope进行sort吗?
【在 a***9 的大作中提到】
: 这题好像本版见过。
: 就是对每两个点算slope和intersect,然后sort.
: 如果允许误差就直接把float sort,否则用分数表示。。
|
a***9
发帖数: 364 | 8 呃。。那还算intersect干嘛
【在 r****o 的大作中提到】
: 请问sort是对slope进行sort吗?
|
r****o
发帖数: 1950 | 9 那是先对slope sort, 如果一样(误差小于给定值)再对intersect sort?
【在 a***9 的大作中提到】
: 呃。。那还算intersect干嘛
|
a***9
发帖数: 364 | 10 嗯，我想大概是这样的。。
【在 r****o 的大作中提到】
: 那是先对slope sort, 如果一样(误差小于给定值)再对intersect sort?
|
r****o
发帖数: 1950 | 11 那复杂度是O(n^2lgn). 这题是不是不能用hash?
【在 a***9 的大作中提到】
: 嗯，我想大概是这样的。。
|
a***9
发帖数: 364 | 12 不是说好于O(n^3)就行了吗。。
我不知道能不能用hash,总觉得hash这种东西对算法题上比较扯。。
大概可以跟recruiter聊一聊是真的。。
【在 r****o 的大作中提到】
: 那复杂度是O(n^2lgn). 这题是不是不能用hash?
|
h**6
发帖数: 4160 | 13 如果坐标都是整数的话，可以把求dy/dx最大公约数然后约分，hash或排序分母，分母
相同再比较分子。这样可以避免浮点数。 |
