algorithm - 采访Q : Given m station and n house, 输出每栋房子最近的k站

Question

有m个站和n个房子，给定每个站和房子的(x,y)坐标，输出每个房子最近的站。

后来，这个问题被概括为寻找离每个房子最近的 k 个车站。

我的看法:对于每个房子，建立一堆距离(自下而上)到车站，然后弹出 k。对所有房屋执行相同的操作。O(n*(m+klogm));

或者，对于每个房子，建立一个到站的顺序统计树，然后寻找有排名的节点并遍历该节点下的整个树。对所有房屋执行相同的操作。O(n*(mlogm+logm+k))

有没有更好的替代方案？任何基于图 DS 的解决方案，哪个比这个更好？

Answer 1

这听起来是使用 k-d tree 的绝佳地点, quadtree , 或其他空间划分树。 “找到最近某个测试点的 k 个对象”的问题称为 k 最近邻问题，这两种数据结构非常有效地解决了这个问题。它们的实现也相当简单。

具体来说:在站外构建一个 k-d 树或四叉树。然后，对于每个房子，在数据结构中对该房子进行 k 最近邻查询，以找到最近的车站。

希望这对您有所帮助!