采访问:给定m站和n户，每栋房子输出最近的k站。

Question

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

后来，这个问题被概括为从每所房子里找出k个最近的车站。

我的观点是:对于每一所房子，都要建一堆距离(从下到上)，然后弹出k，对所有的房子都这样做。O(n*(m+klogm))；

或者，对于每一个房子，建立一个订单统计树到站，然后寻找节点的排名和遍历整个树下的节点。对所有的房子都要这样做。O(n*(mlogm+logm+k))

有什么更好的选择吗？任何基于图DS的解决方案，哪个比这个更好？

Answer 1

这听起来是使用k-d树、四叉树或其他空间分区树的最佳位置。“k-最近邻问题”被称为k-最近邻问题，这两种数据结构有效地解决了这一问题。它们的实现也相当简单。

具体而言:在车站外建一棵k-d树或四叉树.然后，对于每栋房子，在数据结构中对该房屋执行k近邻查询，以找到最近的站点。

希望这能有所帮助！