样板戏版beat it# Joke - 肚皮舞运动
w*x
1 楼
好像是给一个星系, 知道各个星球的坐标, 能较快的求出距离任何一个星球指定距离内
的所有星球. 较笨的方法是O(n^2)的, 就是算出所有星球的距离
的所有星球. 较笨的方法是O(n^2)的, 就是算出所有星球的距离
m*8
2 楼
r*g
3 楼
任何一个星球？意思就是要把所有信息储存下来？否则的话的你换一个星球就要重新计
算？
算？
M*P
4 楼
火星天气如何？
【在 m*******8 的大作中提到】
: http://www.tudou.com/programs/view/Ru4F8boSJ1c/
: 谁教教我怎么贴视频？
【在 m*******8 的大作中提到】
: http://www.tudou.com/programs/view/Ru4F8boSJ1c/
: 谁教教我怎么贴视频？
K*k
5 楼
等同于用一个堆keep k smallest numbers 那题？
m*8
6 楼
我是第一次看到觉得好好笑，分享一下不给挖？
【在 M*P 的大作中提到】
: 火星天气如何？
【在 M*P 的大作中提到】
: 火星天气如何？
d*t
7 楼
How?
【在 K*****k 的大作中提到】
: 等同于用一个堆keep k smallest numbers 那题？
【在 K*****k 的大作中提到】
: 等同于用一个堆keep k smallest numbers 那题？
l*u
8 楼
问题是兔偶得了啊
【在 m*******8 的大作中提到】
: 我是第一次看到觉得好好笑，分享一下不给挖？
【在 m*******8 的大作中提到】
: 我是第一次看到觉得好好笑，分享一下不给挖？
B*5
9 楼
对给定的一个的话，这个我觉得比较合适
【在 K*****k 的大作中提到】
: 等同于用一个堆keep k smallest numbers 那题？
【在 K*****k 的大作中提到】
: 等同于用一个堆keep k smallest numbers 那题？
w*x
10 楼
搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
后很快能得到解答的方法???
后很快能得到解答的方法???
f*t
11 楼
R+ tree
z*c
12 楼
k-d tree.
A*u
13 楼
求详解
【在 z****c 的大作中提到】
: k-d tree.
【在 z****c 的大作中提到】
: k-d tree.
e*l
14 楼
今天面试的时候还说到这个问题了
worst case是O(nk)的k是最大堆的size
比较好的解法
Google map是分割区域，把整个universe分成N多小区域，然后用个maxRadius去套
worst case是O(nk)的k是最大堆的size
比较好的解法
Google map是分割区域，把整个universe分成N多小区域，然后用个maxRadius去套
A*u
15 楼
搞不明白
为啥需要堆呢
【在 e*********l 的大作中提到】
: 今天面试的时候还说到这个问题了
: worst case是O(nk)的k是最大堆的size
: 比较好的解法
: Google map是分割区域，把整个universe分成N多小区域，然后用个maxRadius去套
为啥需要堆呢
【在 e*********l 的大作中提到】
: 今天面试的时候还说到这个问题了
: worst case是O(nk)的k是最大堆的size
: 比较好的解法
: Google map是分割区域，把整个universe分成N多小区域，然后用个maxRadius去套
l*i
16 楼
voronoi diagram, O(nlogn) but it is too difficult for interview questions
unless you work on computational geometry.
unless you work on computational geometry.
m*q
17 楼
如果是求最近的k个的话，先把每个点和其他点的距离按远近排序，
空间O(n^2)，查找最近的k个复杂度O(k)，如果只查第k个的话O(lgn)
以后很快能得到解答的方法???
【在 w****x 的大作中提到】
: 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
: 后很快能得到解答的方法???
空间O(n^2)，查找最近的k个复杂度O(k)，如果只查第k个的话O(lgn)
以后很快能得到解答的方法???
【在 w****x 的大作中提到】
: 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
: 后很快能得到解答的方法???
n*w
18 楼
这个适合面试的答案。每个点上计算出所有距离排序。
Voronoi diagram，KD tree，Range tree可以在follow up中提到。半个小时白板
coding实现几乎完全不可能。
【在 m**q 的大作中提到】
: 如果是求最近的k个的话，先把每个点和其他点的距离按远近排序，
: 空间O(n^2)，查找最近的k个复杂度O(k)，如果只查第k个的话O(lgn)
:
: 以后很快能得到解答的方法???
Voronoi diagram，KD tree，Range tree可以在follow up中提到。半个小时白板
coding实现几乎完全不可能。
【在 m**q 的大作中提到】
: 如果是求最近的k个的话，先把每个点和其他点的距离按远近排序，
: 空间O(n^2)，查找最近的k个复杂度O(k)，如果只查第k个的话O(lgn)
:
: 以后很快能得到解答的方法???
s*n
19 楼
应该是用size为K的MaxHeap，Head是最小k个里最大的一个。
【在 w****x 的大作中提到】
: 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
: 后很快能得到解答的方法???
【在 w****x 的大作中提到】
: 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
: 后很快能得到解答的方法???
A*c
20 楼
这是经典的Nearest neighbor search的变体。
1：建kdtree
2：走到leaf node，纪录没有走的分支节点
3：trace back。
【在 w****x 的大作中提到】
: 好像是给一个星系, 知道各个星球的坐标, 能较快的求出距离任何一个星球指定距离内
: 的所有星球. 较笨的方法是O(n^2)的, 就是算出所有星球的距离
1：建kdtree
2：走到leaf node，纪录没有走的分支节点
3：trace back。
【在 w****x 的大作中提到】
: 好像是给一个星系, 知道各个星球的坐标, 能较快的求出距离任何一个星球指定距离内
: 的所有星球. 较笨的方法是O(n^2)的, 就是算出所有星球的距离
相关阅读
好心态塑造好心情，好心情塑造最出色的你那个阿玛尼少年被坑了吧過年這些話題真的很不討喜啊~自从机器人组队出现以后为什么香蕉干闻起来一股脚臭味男子买兰博基尼回家过年 半路熄火被困荒山野岭 (转载)大喜 飞面神教正式获得荷兰政府承认VT又出事儿了美国人消费不动了，商店都关门了 (转载)问个问题，发廊为什么都喜欢养植物？请教一下各位，急和尚与尼姑相遇之后(转载)how to get away with murder真实荒诞版你在《上古卷轴》中干过的最惊人的事情是什么？ zhihu人生如戏，请给我好一点儿的演技非洲太恐怖了空军领导：地毯式轰炸lSlS不符合我军价值观奥巴马参拜绿教神社为什么电视里流行男主动不动抓着女主的手一起跑？feitian版笑话109----zz