w****x
发帖数: 2483 | 1 好像是给一个星系, 知道各个星球的坐标, 能较快的求出距离任何一个星球指定距离内
的所有星球. 较笨的方法是O(n^2)的, 就是算出所有星球的距离 |
r*******g
发帖数: 1335 | 2 任何一个星球？意思就是要把所有信息储存下来？否则的话的你换一个星球就要重新计
算？ |
K*****k
发帖数: 430 | 3 等同于用一个堆keep k smallest numbers 那题？ |
d********t
发帖数: 9628 | 4 How?
【在 K*****k 的大作中提到】
: 等同于用一个堆keep k smallest numbers 那题？
|
B******5
发帖数: 4676 | 5 对给定的一个的话，这个我觉得比较合适
【在 K*****k 的大作中提到】
: 等同于用一个堆keep k smallest numbers 那题？
|
w****x
发帖数: 2483 | 6 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
后很快能得到解答的方法??? |
f*******t
发帖数: 7549 | |
z****c
发帖数: 602 | |
A**u
发帖数: 2458 | 9 求详解
【在 z****c 的大作中提到】
: k-d tree.
|
e*********l
发帖数: 136 | 10 今天面试的时候还说到这个问题了
worst case是O(nk)的k是最大堆的size
比较好的解法
Google map是分割区域，把整个universe分成N多小区域，然后用个maxRadius去套 |
|
|
A**u
发帖数: 2458 | 11 搞不明白
为啥需要堆呢
【在 e*********l 的大作中提到】
: 今天面试的时候还说到这个问题了
: worst case是O(nk)的k是最大堆的size
: 比较好的解法
: Google map是分割区域，把整个universe分成N多小区域，然后用个maxRadius去套
|
l***i
发帖数: 1309 | 12 voronoi diagram, O(nlogn) but it is too difficult for interview questions
unless you work on computational geometry. |
m**q
发帖数: 189 | 13 如果是求最近的k个的话，先把每个点和其他点的距离按远近排序，
空间O(n^2)，查找最近的k个复杂度O(k)，如果只查第k个的话O(lgn)
以后很快能得到解答的方法???
【在 w****x 的大作中提到】
: 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
: 后很快能得到解答的方法???
|
n*******w
发帖数: 687 | 14 这个适合面试的答案。每个点上计算出所有距离排序。
Voronoi diagram，KD tree，Range tree可以在follow up中提到。半个小时白板
coding实现几乎完全不可能。
【在 m**q 的大作中提到】
: 如果是求最近的k个的话，先把每个点和其他点的距离按远近排序，
: 空间O(n^2)，查找最近的k个复杂度O(k)，如果只查第k个的话O(lgn)
:
: 以后很快能得到解答的方法???
|
s******n
发帖数: 3946 | 15 应该是用size为K的MaxHeap，Head是最小k个里最大的一个。
【在 w****x 的大作中提到】
: 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
: 后很快能得到解答的方法???
|
A*********c
发帖数: 430 | 16 这是经典的Nearest neighbor search的变体。
1：建kdtree
2：走到leaf node，纪录没有走的分支节点
3：trace back。
【在 w****x 的大作中提到】
: 好像是给一个星系, 知道各个星球的坐标, 能较快的求出距离任何一个星球指定距离内
: 的所有星球. 较笨的方法是O(n^2)的, 就是算出所有星球的距离
|
