w*5
2 楼
一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
能最后无法被配对。有没有算法使得能配对的点最多？
follow-up是求出最小的k，使得所有点都能配上对。
这个应该怎么考虑？
能最后无法被配对。有没有算法使得能配对的点最多？
follow-up是求出最小的k，使得所有点都能配上对。
这个应该怎么考虑？
H*1
3 楼
G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
Now what you are looking at are matchings, so just apply Edmonds' algorithm.
O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
improve the algorithm, google or wait till DaNiu post an answer.
For finding the smallest k, there are probably smarter ways, but a 糙快猛
practical solution could be:
Find d = closest pair distance O(nlgn)
Find D = farthest pair distance O(nlgn)
Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
Now what you are looking at are matchings, so just apply Edmonds' algorithm.
O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
improve the algorithm, google or wait till DaNiu post an answer.
For finding the smallest k, there are probably smarter ways, but a 糙快猛
practical solution could be:
Find d = closest pair distance O(nlgn)
Find D = farthest pair distance O(nlgn)
Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
w*5
4 楼
多谢大牛
algorithm.
【在 H*******1 的大作中提到】
: G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
: Now what you are looking at are matchings, so just apply Edmonds' algorithm.
: O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
: improve the algorithm, google or wait till DaNiu post an answer.
: For finding the smallest k, there are probably smarter ways, but a 糙快猛
: practical solution could be:
: Find d = closest pair distance O(nlgn)
: Find D = farthest pair distance O(nlgn)
: Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
algorithm.
【在 H*******1 的大作中提到】
: G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
: Now what you are looking at are matchings, so just apply Edmonds' algorithm.
: O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
: improve the algorithm, google or wait till DaNiu post an answer.
: For finding the smallest k, there are probably smarter ways, but a 糙快猛
: practical solution could be:
: Find d = closest pair distance O(nlgn)
: Find D = farthest pair distance O(nlgn)
: Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
l*n
5 楼
这是哪儿的面试题？
还是课程作业
【在 w********5 的大作中提到】
: 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
: 能最后无法被配对。有没有算法使得能配对的点最多？
: follow-up是求出最小的k，使得所有点都能配上对。
: 这个应该怎么考虑？
还是课程作业
【在 w********5 的大作中提到】
: 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
: 能最后无法被配对。有没有算法使得能配对的点最多？
: follow-up是求出最小的k，使得所有点都能配上对。
: 这个应该怎么考虑？
b*m
6 楼
奇数个点，多大的k也不行呀。
相关阅读
ds和sde如何选择【活动】大数据男神进阶全攻略 – 对话来自Apple和Mixpanel的大数据工程师Open contest for a mobile ski app学习spark是否需要懂scala？数据分析, DA,DS,SI需学什编程langugage俄罗斯人也很猛，人家的wiki里各种书直接下载pdf周一美西六点半，海外华人公益职场问答网会106个热门mid-sized it公司推荐 (转载)可以通过jdbc给hive table 进行 load data么？Postdoctoral Fellowship at UConnoffer 求助Webinar info机器学习周报 2015-02-08求问一道关于NLP的面试题如果你聽到大數據、雲計算，你要盡可能的逃離问一个统计算average from ranges (转载)求助： windows 下java 用 jdbc连接hive 老是抱错有关归类一个面试题（predictive model） (转载)谁知道Eric Baldeschwieler (Hadoop) 的联系方式？