假设在一个N×N的地图里面，有N个建筑物，已经给出每个建筑物的坐标
然后要求输入随便一个坐标点x（a,b)
要求输出离 x 最近的建筑物
要求:这道题要求找出比O(N)更好的方法，不能把x跟全部建筑物的距离都比一遍。
然后要求输入随便一个坐标点x（a,b)
要求输出离 x 最近的建筑物
要求:这道题要求找出比O(N)更好的方法，不能把x跟全部建筑物的距离都比一遍。
This topic created in 4074 days ago, the information mentioned may be changed or developed.
 |
1
sonicwu Mar 21, 2015 via iPhone
如果 O(N) 这个 N 指的是建筑物数量，那么 GeoHash 就可以吧
|
 |
2
efi Mar 21, 2015 via Android
kdtree
|
 |
3
ETiV Mar 21, 2015
GeoHash +1
不过GeoHash有边界问题, 只能先找出点 x 附近的 M 个建筑物, 再从这M建筑物里算距离, 取最近. |
 |
4
budlion Mar 21, 2015
这是阿里的面试题么。。。我也被这道题干过。。。
|
 |
5
yangkeao Mar 21, 2015
话说输入不是就已经N了吗。。。。其实我不会算法复杂度。。都是Feel的。。。
|
 |
6
shuding Mar 21, 2015
二楼 k-d tree 正解，（随机数据下单次查询）期望复杂度可到 O(Sqrt(N))……
|
 |
7
zhyu Mar 21, 2015 via iPhone
除了 kd tree 和 geohash，还可以用 voronoi diagram
|
 |
8
thinker3 Mar 21, 2015  1
|
 |
9
liubiantao Mar 21, 2015 via iPhone
能不能用空间换时间，提前算好，然后就是O(1)了
|
 |
10
ffffwh Mar 22, 2015
这玩意要是不知道，能靠自己想出来么（面试当场/n天）。。。
别剧透让我想想 |
 |
11
Valyrian Mar 22, 2015
Voronoi diagram，Computational Geometry的经典问题
|
 |
12
stockss Mar 22, 2015
很简单，构造一个权为1的矩阵图，然后计算各个建筑距离x的距离，取最小即可
|
 |
13
ryd994 Mar 22, 2015
螺旋一圈圈向外搜索呢？
|
 |
14
Exin Mar 22, 2015 via iPhone
想了半天才发现，优于O(N)应该是对于查询操作的要求
|
Select Language