b******7
发帖数: 79 | 1 Given a set of points (x,y) , find all pairs of points whose distance is
less than a given number, say, K.
这个题brute force： 对每个点，求和其他点距离，O(N^2),不知道哪位大侠有高见啊
？请不吝赐教！万分感激！ | s*******i
发帖数: 712 | 2 对啊，我也想问这题。面经里出现好几次，每次出现大家都说很old。就是没一个人给
个答案的。
【在 b******7 的大作中提到】
: Given a set of points (x,y) , find all pairs of points whose distance is
: less than a given number, say, K.
: 这个题brute force： 对每个点，求和其他点距离，O(N^2),不知道哪位大侠有高见啊
: ？请不吝赐教！万分感激！
| a**********s
发帖数: 588 | 3 这个用quad tree解最好, 复杂度是相对于结果大小来说linear的 | b****a
发帖数: 4465 | 4 sort the data, then a binary search? | g*******y
发帖数: 1930 | 5 我觉得应该也能用closest pair的思路来做吧
我感觉quadtree的思路就是closest pair的思路的二维版
【在 a**********s 的大作中提到】
: 这个用quad tree解最好, 复杂度是相对于结果大小来说linear的
| a******h
发帖数: 19 | 6 KD-tree is also able to find the solution. | b******7
发帖数: 79 | | b******7
发帖数: 79 | | a*****r
发帖数: 55 | | m*****f
发帖数: 1243 | 10 我详细说说吧， 就是closest pair的思路
1. 在x轴上排序
2. 取中点x_middle把点分成左半边和右半边
3. 递归寻找左半边和右半边距离小于k得pair
4. 同时还有一边在左，一边在右的pair,
5. 3+4 = all answer
其他都是O(nlogn)没问题， 第四步如果强解一样是o(n^2), 但是因为有条件是小于k,
那么只要考虑 x > x_middle-k 的左边点和 x < x_middle +k 的右边点即可，
并且对某个x_left, 只需考虑
x_middle < x_right < x_middle + k - (x_middle-x_left)
的右边点， 可知是O(n).
应该没错把 | n******r
发帖数: 1247 | 11 没觉得x轴上排序会有什么用
如果k等于最远两点间的距离
那么找出最远的两个点已经是0（N^2）复杂度了
,
【在 m*****f 的大作中提到】
: 我详细说说吧， 就是closest pair的思路
: 1. 在x轴上排序
: 2. 取中点x_middle把点分成左半边和右半边
: 3. 递归寻找左半边和右半边距离小于k得pair
: 4. 同时还有一边在左，一边在右的pair,
: 5. 3+4 = all answer
: 其他都是O(nlogn)没问题， 第四步如果强解一样是o(n^2), 但是因为有条件是小于k,
: 那么只要考虑 x > x_middle-k 的左边点和 x < x_middle +k 的右边点即可，
: 并且对某个x_left, 只需考虑
: x_middle < x_right < x_middle + k - (x_middle-x_left)
| f*********r
发帖数: 68 | 12 这题问的有问题吧. 如果让你输出all pairs of points whose distance is
less than a given number K. 显然是O(N^2).
是不是应该问find K pairs of points with smallest distance. 这个有比O(N^2)好
的算法.
【在 b******7 的大作中提到】
: Given a set of points (x,y) , find all pairs of points whose distance is
: less than a given number, say, K.
: 这个题brute force： 对每个点，求和其他点距离，O(N^2),不知道哪位大侠有高见啊
: ？请不吝赐教！万分感激！
| k***e
发帖数: 556 | 13 quad tree, kd tree都是computational geometry里面的内容。你们怎么都这么牛x？
令人发指的强啊 |
|
