找到离原点最近的 100 颗恒星的算法

Question

首先让我说出正确的问题:

问:有一个文件包含超过一百万个点 (x,y)，每个点代表一颗星。在 (a,b) 处有一个行星地球。现在，任务是建立一个算法，返回距离地球最近的 100 颗恒星。您的算法的时间和空间复杂度是多少。

这个问题在各种面试中被问过很多次。我试着查找答案，但找不到满意的答案。

一种方法，我认为可能是使用大小为 100 的最大堆。计算每个星的距离并检查距离是否小于最大堆的根。如果是，将其替换为根并调用 heapify。

还有其他更好/更快的答案吗？

P.S:这不是作业题。

Answer 1

您实际上可以在时间 O(n) 和空间 O(k) 中执行此操作，其中 k 是您想要的最近点的数量，方法是使用一个非常聪明的技巧。

selection problem 如下:给定一个元素数组和一些索引 i，重新排列数组的元素，使得第 i 个元素在正确的位置，所有小于第 i 个元素的元素都在左边，并且所有元素大于第 i 个元素在右边。例如，给定数组

40  10  00  30  20

如果我尝试根据索引 2(零索引)进行选择，一个结果可能是

10  00  20  40  30

由于索引为2(20)的元素在右边，左边的元素小于20，右边的元素大于20。

事实证明，由于这比实际排序数组的要求更宽松，因此可以在 O(n) 的时间内完成此操作，其中 n 是数组元素的数量。这样做需要一些复杂的算法，例如 median-of-medians算法，但确实是O(n)时间。

那么你如何在这里使用它呢？一种选择是将文件中的所有 n 个元素加载到一个数组中，然后使用选择算法在 O(n) 时间和 O(n) 空间中选择前 k 个(这里，k = 100)。

但实际上你可以做得比这更好!对于您想要的任何常量 k，维护一个包含 2k 个元素的缓冲区。从文件中加载 2k 个元素到数组中，然后使用选择算法重新排列它，使得最小的 k 个元素在数组的左半部分，最大的在右半部分，然后丢弃最大的 k 个元素(它们可以' t 是 k 个最近点中的任何一个)。现在，将文件中的 k 个元素加载到缓冲区中，然后再次进行此选择，并重复此操作，直到处理完文件的每一行。每次进行选择时，您都会丢弃缓冲区中最大的 k 个元素，并保留您目前看到的 k 个最接近的点。因此，在最后，您可以最后一次选择前k个元素并找到前k个。

新方法的复杂性如何？好吧，您正在使用 O(k) 内存作为缓冲区和选择算法。您最终会在大小为 O(k) 的缓冲区上调用 select 总共 O(n/k) 次，因为您在读取 ​​k 个新元素后调用了 select 。由于选择大小为 O(k) 的缓冲区需要时间 O(k)，因此此处的总运行时间为 O(n + k)。如果 k = O(n)(一个合理的假设)，这需要时间 O(n)，空间 O(k)。

希望这对您有所帮助!