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