h*****g
发帖数: 312 | 1 You are given a list of points in the plane, write a program that
outputs each point along with the point that are closest
to it.
The order is less then O(n^2) .
For example, given a set of points where each line is of the form:
ID x-coordinate y-coordinate
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
Your program should output:
1 2
2 1
3 1
4 1
5 4 |
l*********8
发帖数: 4642 | 2 如果要求O(n^2), 那么最naive办法都可以了。
如果要快些的话，好像可以用Quad-tree.
【在 h*****g 的大作中提到】
: You are given a list of points in the plane, write a program that
: outputs each point along with the point that are closest
: to it.
: The order is less then O(n^2) .
: For example, given a set of points where each line is of the form:
: ID x-coordinate y-coordinate
: 1 0.0 0.0
: 2 10.1 -10.1
: 3 -12.2 12.2
: 4 38.3 38.3
|
h*****g
发帖数: 312 | 3 我看到 一种 nlogn 的解法，但感觉不对。。
Approach:
First Have all the points in an array and sort them according to their X
axis, which would give:
3 -12.2 12.2
1 0.0 0.0
2 10.1 -10.1
4 38.3 38.3
5 79.99 179.99
Then for every point P, calculate the distance from 1 point in the front and
1 point in the back:
For Ex: Point with Id=3 (-12.2, 12.2) does not have 1 point
in the back.
Always store only min distance and the corresponding point Ids
Then Sort the points according to their Y Axis, which would give:
2 10.1 -10.1
1 0.0 0.0
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
然后 do the same procedure as X 坐标。
Total complexity: 2nlogn + 4kn + klogk = O(nlogn)
k = 1 here.
【在 l*********8 的大作中提到】
: 如果要求O(n^2), 那么最naive办法都可以了。
: 如果要快些的话，好像可以用Quad-tree.
|
d***o
发帖数: 181 | 4 你总要计算任意两个pair之间的值吧，这样就是O(n^2)
如果比上面的要小，倒是可以计算任意点到原点的距离，排序一下，排除所有与该点距
离之差大于与最小距离之和的点，然后再找最小距离点，不过最坏情况也是O(n^2) |
f*****i
发帖数: 835 | |
l***i
发帖数: 1309 | 6 Jon Bentley's phd dissertation from UNC has the solution. Honestly it is way
too difficult for an interview. the problem is called all pair nearest
neighbor or simply All NN. Facebook puzzle used to have such a problem but
for that one you can get Accepted by some pruning in search. |
