样板戏版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)的, 就是算出所有星球的距离
相关阅读
Re: 她和老公做爱，高潮时分高声赞美主！ (转载)国内西部真是有穷地方，不是传说！！ (转载)zz“换了一张膜，一切重新开始！”…………House M.D，笑死了微博控是这么开始吃饭的我觉得老邢这个bbs可能是个大生意阿毛少将在卧薪尝胆 (转载)华西村：毛主席、耶稣、佛祖并立 书记每日演讲分毫不差 (转载)动物也有不伦之恋：云南动物园上演“羊鹿恋”0结果的google搜索条目ccav news被American Express Small Business害惨了 (转载)给树袋熊挠痒痒Herman Cain has not sexually harassed me, even though I am attractive加州坠入高铁陷阱不可自拔洪博培女儿在脸书网站高调示爱，疑与薄瓜瓜接近结婚 (转载)拉登之死新说WSN励志篇：高考落榜生获美国国务卿一万美元小费有没有搞错？！.huntsman的女儿比晓丹差一条街 (转载)