t*****s
发帖数: 416 | 1 给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
点。
距离的定义是X轴距离+Y轴距离。 |
g*******s
发帖数: 2963 | 2 有优于O(n)的解法？
【在 t*****s 的大作中提到】
: 给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
: 点。
: 距离的定义是X轴距离+Y轴距离。
|
t****d
发帖数: 423 | 3 以给出的点为中心的一个选择45度的正方形，边长k(2)^(1/2),
★ 发自iPhone App: ChineseWeb 7.8
【在 t*****s 的大作中提到】
: 给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
: 点。
: 距离的定义是X轴距离+Y轴距离。
|
t*****s
发帖数: 416 | 4 如果只求一次解应该没有。但是如果多次求解的话应该有预处理以后缩小单次查找时间
的算法。
【在 g*******s 的大作中提到】
: 有优于O(n)的解法？
|
t*****s
发帖数: 416 | 5 我可能没说清楚。网格只在概念中存在。有的数据只是N组坐标。
【在 t****d 的大作中提到】
: 以给出的点为中心的一个选择45度的正方形，边长k(2)^(1/2),
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
s*******r
发帖数: 2697 | 6 多次查找的话，先sort 就可以吧
【在 t*****s 的大作中提到】
: 如果只求一次解应该没有。但是如果多次求解的话应该有预处理以后缩小单次查找时间
: 的算法。
|
t*****s
发帖数: 416 | 7 我当时做出来的就是按照一个轴先排序，然后二分查找到该节点，在该轴上往两边找最
多K个长度。这样预处理是O(nlogn),单次是O(logn)+O(k)。
但是印象中在哪儿看过类似的题，这个好像不是最优解。听面试官的意思这个问题还可
以拓展到多个dimension。
【在 s*******r 的大作中提到】
: 多次查找的话，先sort 就可以吧
|
s******n
发帖数: 124 | 8 range search? 用ball tree/kd-tree |
