t****a
发帖数: 1212 | 1 Given a 2 dimensional plane in which there are n points. Give an algorithm
to
generate the equation of a line that divides the plane such that there are n
/2 points
on one side and n/2 points on the other. |
S******n
发帖数: 590 | 2 分类器
n
【在 t****a 的大作中提到】
: Given a 2 dimensional plane in which there are n points. Give an algorithm
: to
: generate the equation of a line that divides the plane such that there are n
: /2 points
: on one side and n/2 points on the other.
|
t****a
发帖数: 1212 | 3 Man, could you explain it a little bit more that someone can implement it.
【在 S******n 的大作中提到】
: 分类器
:
: n
|
h**k
发帖数: 3368 | 4 分类器处理的问题不同。对于分类器，输入的点本来就标定为两类。这个问题中输入点
没有区别。
【在 S******n 的大作中提到】
: 分类器
:
: n
|
h**k
发帖数: 3368 | 5 如果用二分法，似乎可以做到O(n)。
选一个新点，在所有的输入的n个点的左下方。然后计算每个输入点到新点的连线的斜
率，得到一个大小为n的实数数组。现在题目变为在这个数组中找median element。
n
【在 t****a 的大作中提到】
: Given a 2 dimensional plane in which there are n points. Give an algorithm
: to
: generate the equation of a line that divides the plane such that there are n
: /2 points
: on one side and n/2 points on the other.
|
t****a
发帖数: 1212 | 6 这个办法挺好。
但是如果多个斜率相等且等于median element的时候，这条线无法分开那些点。
【在 h**k 的大作中提到】
: 如果用二分法，似乎可以做到O(n)。
: 选一个新点，在所有的输入的n个点的左下方。然后计算每个输入点到新点的连线的斜
: 率，得到一个大小为n的实数数组。现在题目变为在这个数组中找median element。
:
: n
|
h**k
发帖数: 3368 | 7 在线上的点其实可以看成在线的哪一边都行。
如果面试官一定要深究，可以这么做。假设在这条直线上一共有m个点，直线一边是k个
点，则另一边是n-k-m个点。找到直线上的第n/2-k个点，然后以这个点重新构建一个直
线，它的斜率和原来的直线斜率相差一个极小值，并使得m个点中的前n/2-k点和k点在
直线的一边。
【在 t****a 的大作中提到】
: 这个办法挺好。
: 但是如果多个斜率相等且等于median element的时候，这条线无法分开那些点。
|
h**6
发帖数: 4160 | 8 先根据x坐标排序，找出中值，作一条与x轴垂直的线。
然后检查是否有点落在这条线上，如果有，就再找出线上所有点的y坐标中值，然后以
此为轴稍稍旋转一个角度即可。 |
