首先让我提出正确的问题：
问：有一个文件包含超过一百万个点 (x,y)，每个点代表一颗星星。 (a,b) 处有一颗行星地球。现在，任务是构建一种算法，返回距离地球最近的 100 颗恒星。您的算法的时间和空间复杂度是多少？
这个问题在各种采访中被问过很多次。我尝试查找答案，但找不到满意的答案。
我认为一种方法可能是使用大小为 100 的最大堆。计算每颗星的距离并检查距离是否小于最大堆的根。如果是，则将其替换为 root 并调用 heapify。
还有其他更好/更快的答案吗？
PS：这不是家庭作业问题。
实际上，您可以通过使用非常聪明的技巧，在时间 O(n) 和空间 O(k) 中完成此操作，其中 k 是您想要的最近点的数量。
The 选择问题 http://en.wikipedia.org/wiki/Selection_algorithm如下：给定一个元素数组和某个索引 i，重新排列数组的元素，使得第 i 个元素位于正确的位置，所有小于第 i 个元素的元素位于左侧，所有大于第 i 个元素的元素位于左侧元素位于右侧。例如，给定数组
40 10 00 30 20
如果我尝试基于索引 2（零索引）进行选择，结果可能是
10 00 20 40 30
由于索引 2 (20) 处的元素位于正确的位置，因此左侧的元素小于 20，右侧的元素大于 20。
事实证明，由于这比实际对数组进行排序的要求不太严格，因此可以在 O(n) 时间内完成此操作，其中 n 是数组元素的数量。这样做需要一些复杂的算法，例如中位数的中位数 http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm算法，但确实是 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)。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
