算法来寻找最接近100明星原点

问：有包含超过一百万点（X，Y），其中每一个代表一个明星的文件。（a，b）处有一颗行星地球。现在，任务是构建一个算法，将最接近的100颗恒星返回到地球。算法的时间和空间复杂度是多少？

这个问题已经多次在各种采访中被问到。我试图查找答案，但找不到满意的答案。

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

其他更好/更快的答案？

P.S：这不是一个家庭作业问题。

2012-02-08 noMAD

[在长度为n的列表中查找x个最小整数]的可能重复（http://stackoverflow.com/questions/3764355/find-the-x-smallest-integers-in-a-list-of-长度-n） – hugomg 2012-02-08 22:16:43

是的，可惜。这是一个有趣的问题，但已经在这里回答。 – 2012-02-08 22:21:24

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

实际上，您可以通过使用非常聪明的技巧在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 = 100）中选择最高k值。

但你实际上可以做得比这更好！对于任何你想要的常量k，保持2k个元素的缓冲区。将文件中的2k个元素加载到数组中，然后使用选择算法重新排列它，使得最小的k个元素位于数组的左半部分，最大的位于右侧，然后丢弃最大的k个元素（它们可以' t是k个最近点中的任何一个）。现在，从文件中加载k个更多的元素到缓冲区中并再次执行此选择，并重复此操作，直到处理完文件的每一行。每次您做出选择时，都放弃缓冲区中最大的k个元素，并保留迄今为止所见到的k个最近点。因此，最后，您可以最后一次选择前k个元素并查找前k个元素。

新方法的复杂性是什么？那么，你使用O（k）内存作为缓冲区和选择算法。由于您在读取k个新元素之后调用select，因此最终调用select O（k）总共为O（n/k）次的缓冲区。由于在一个大小为O（k）的缓冲区上选择需要时间O（k），因此这里的总运行时间是O（n + k）。如果k = O（n）（一个合理的假设），这需要时间O（n），空间O（k）。

希望这会有所帮助！

来源

2012-02-08 22:20:40 templatetypedef

谢谢，我确实学到了一些东西:) – noMAD 2012-02-08 22:35:20

对此，我会添加一个优化。在向缓冲区添加新元素之前，如果它大于先前迭代中找到的第k个最大值，则丢弃该元素。在这个“大于”测试中，您可以在测试实际距离之前首先检查单个坐标是否较大。这根本不会改变big-O，但它避免了大量的距离计算，并且平方根操作相当缓慢。所以你得到一个更好的常数。 – btilly 2012-02-08 22:40:52

@btilly：由于sqrt是一个单调函数，您可以随时避免sqrt操作。使距离最小化的点也使距离平方最小化（正方形消除sqrt）。 – 2012-02-08 23:03:22

这是一个著名的问题，并出现了很多解决的为： http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

，如果你没有发现它是有用的，还有一些其他的资源，如Rurk的计算几何的书。

来源

2012-02-08 22:34:08 orezvani

查询点在这种情况下是已知的，所以我们甚至不必去knn。 – 2012-02-08 23:43:23

你的算法是正确的。请记住，程序的时间复杂度为O（n。log 100）= O（n），除非找到最近点的数量可能会有所不同。

来源

2012-02-08 23:48:28

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()

来源

2015-06-01 18:24:11 aertoria

我刚刚在Python中为您的问题编码，希望它有帮助 – aertoria 2015-06-01 18:25:53

为了详细说明的MaxHeap溶液你将建立一个最大堆与来自文件（在这种情况下，K = 100）中的前k个元素。

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

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

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

这将花费O（（n-k）logk）时间来完成。最后，我们只剩下最大堆中的k个元素。你可以调用heapify k次来返回所有这些k元素。这是另一个O（klogk）。总体时间复杂度为O（k +（nk）logk + klogk）。

来源

2015-07-27 16:41:44

算法来寻找最接近100明星原点

回答

相关问题