寻找距离原点最近的100颗星星的算法

Question

首先让我正确地表达问题:

问题：有一个包含超过一百万个点（x，y）的文件，每个点代表一颗星。地球位于（a，b）上。现在，任务是构建一种算法，该算法将返回距离地球最近的100颗星。你的算法的时间和空间复杂度会是多少？

这个问题已经在各种面试中问了很多次。我尝试查找答案，但没有找到令人满意的答案。

我想到的一种方法是使用大小为100的最大堆。计算每颗星的距离，并检查距离是否小于最大堆的根节点。如果是，则用该点替换根节点并调用heapify。

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

P.S: 这不是一个作业问题。

- noMAD

---

可能是重复的问题：在长度为n的列表中找到x个最小的整数。 - hugomg

是的，有点可惜。这是一个有趣的问题，但已经在这里得到了回答。 - Daniel Fischer

@missingno：有点类似，但那个问题可以很容易地通过我上面提供的解决方案来解决。在这里，需要进行一些额外的计算，我想知道是否有一种方法可以将它们最小化。 - noMAD

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个元素（它们不能是任何k个最近点之一）。现在，从文件中再加载k个元素到缓冲区中，并再次进行此选择，重复此过程，直到处理完文件的每一行。每次进行选择时，您都会丢弃缓冲区中最大的k个元素，并保留到目前为止看到的k个最近点。因此，在最后，您可以最后一次选择前k个元素，并找到前k个。

新方法的复杂度是多少？嗯，您正在使用O（k）的缓冲区和选择算法内存。由于读取k个新元素后调用select，因此您总共会在大小为O（k）的缓冲区上调用O（n / k）次select。由于在大小为O（k）的缓冲区上选择需要O（k）时间，因此这里的总运行时间为O（n + k）。如果k = O（n）（合理的假设），则需要O（n）时间，空间O（k）。

希望这有所帮助！

- templatetypedef

---

我想再加上一种优化方法。在将新元素添加到缓冲区之前，如果它比之前迭代中找到的第k大的元素还要大，则将其丢弃。在这个“比较大小”的测试中，您可以先检查任何一个坐标是否更大，然后再测试实际距离。这不会改变大O表示法，但它避免了很多距离计算，而平方根运算相当慢。因此，您可以获得更好的常数。 - btilly

@btilly：你总是可以避免使用sqrt操作，因为sqrt是单调函数。最小化距离的点也会最小化距离的平方（平方会抵消sqrt）。 - Rob Neuhaus

@rrenaud 你说得对。然而，乘法仍然比比较更昂贵，因此避免平方仍然是值得的。 - btilly

优秀的算法和解释。 - Håvard Geithus

你是怎么决定使用“2倍K”元素的？为什么不用“3倍K”或其他类似的东西呢？ - Darth.Vader

@user721998- 任何大于k的固定倍数都可以使用。选择的数量为n / ((m - 1)k)，其中m是倍数，由于每个选择需要O(k)时间，因此总运行时间为O(n / (m-1))，空间使用量为O(mk)。我选择了2，因为它是一个容易处理的数字。好问题！ - templatetypedef

Answer 2

为了详细说明MaxHeap解决方案，您需要使用文件中的前k个元素（在本例中，k = 100）构建一个最大堆。

最大堆的关键是其与地球（a，b）的距离。可以使用以下公式计算2D平面上2点之间的距离：

dist = (x1,y1) to (x2,y2) = square_root((x2 - x1)^2 + (y2 - y1)^2); 

这将花费O(k)的时间来构建。对于从k到n的每个后续元素，即(n-k)个元素，您需要获取其距离地球的距离，并将其与max-heap的顶部进行比较。如果要插入的新元素比max-heap的顶部更接近地球，请替换max-heap的顶部并在堆的新根上调用heapify。

这将花费O((n-k)logk)的时间来完成。最后，我们只剩下max-heap中的k个元素。您可以调用k次heapify来返回所有这些k个元素。这又是一个O(klogk)。

总体时间复杂度将是O(k + (n-k)logk + klogk)。

- Abhi Tk

Answer 3

import sys,os,csv

iFile=open('./file_copd.out','rU')
earth = [0,0]



##getDistance return distance given two stars
def getDistance(star1,star2):
    return sqrt((star1[0]-star2[0])**2 +(star1[1]-star2[1])**2 )


##diction dict_galaxy looks like this  {key,distance}  key is the seq assign to each star, value is a list [distance,its cordinance]
##{1,[distance1,[x,y]];2,[distance2,[x,y]]}
dict_galaxy={}
#list_galaxy=[]
count = 0
sour=iFile.readlines()
for line in sour:
    star=line.split(',')   ##Star is a list [x,y]
    dict_galaxy[count]=[getDistance(earth,star),star]
    count++

###Now sort this dictionary based on their distance, and return you a list of keys.
list_sorted_key = sorted(dict_galaxy,key=lambda x:dict_galaxy[x][0])

print 'is this what you want %s'%(list_sorted_key[:100].to_s)
iFile.close()

- aertoria

---

我刚刚用Python为您的问题编写了这个，希望能有所帮助。 - aertoria

Answer 4

这是一个著名的问题，有很多解决方案： http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

如果你觉得这些不够用，还有其他资源，比如 Rurk 的计算几何书。

- orezvani

---

在这种情况下，查询点已知，因此我们甚至不必去knn。 - Sid Datta

Answer 5

你的算法是正确的。只要记住，除非要查找的最近点数目可能会变化，否则你程序的时间复杂度为O(n . log 100 ) = O(n)。

- Sid Datta