面试问题：给定m个车站和n个房屋，输出每个房屋最近的k个车站。

Question

有m个站和n个住宅，给出每个站和住宅的(x,y)坐标，输出每个住宅的最近站点。

后来，这个问题被推广为从每个住宅中找到k个最近的站点。

我的想法是：对于每个住宅，建立一个到站点的距离堆（自下而上），然后弹出最接近的k个。对所有住宅执行相同的操作。O(n*(m+klogm))；

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

是否有更好的选择？是否有基于图形数据结构的解决方案比这更好？

- claudius

---

“构建一个顺序统计树”是这个问题的替代解决方案吗？如果是，请在问题中明确指出。如果它是解决方案的一部分，为什么不直接查找所有距离小于使用堆找到的第k近站点的站点呢？ - Bernhard Barker

Answer 1

这听起来是一个使用k-d树，四叉树或其他空间划分树的绝佳场所。 "查找离某个测试点最近的k个对象" 的问题被称为k最近邻问题，这两种数据结构可以非常高效地解决它。它们也相对容易实现。

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

希望这有所帮助！

- templatetypedef

---

请添加一个关于四叉树的简短描述，以及它为二维搜索提供了什么有用的功能。 - arunmoezhi

@arunmoezhi 我觉得在这里很难给出简短的描述，而不是有效地重复如何在四叉树中进行k-NN搜索。这些信息可能可以通过快速的谷歌搜索找到。 - templatetypedef

那只是一种观点，以便你的答案看起来完整。 - arunmoezhi

我对四叉树不是很熟悉，但简要介绍一下k-d树以及如何使用它找到(k)个最近邻居应该不会太长，并且有助于使这个答案更加自包含。相关的元讨论. - Bernhard Barker

@Dukeling 我其实不确定我是否同意这个元答案 - 我曾在我教授的一门课中布置了编程 k-d 树作为编程作业，需要大约 12 页左右的图表来完全描述 k-d 树如何工作、直觉是什么以及 k-NN 算法如何工作。老实说，我认为我无法在这里总结这些内容，而且我所提供的任何关于 k-d 树或四叉树的工作原理的信息都不足以解释它们上面的 k-NN 算法。 - templatetypedef

它不必提供足够的细节来实现它自己，只需基本的理念即可（例如，维基百科中的“最近邻搜索”部分的“非正式描述”和项目3可能可以简化为一两个句子，并稍微扩展到k个最近邻居，还有可能包括3张图片） - 不过，你选择做与否完全取决于你。 - Bernhard Barker