来源:AMAZON访谈问题
给定二维空间中的点P和其他N个点，从最接近P的的N个点中找到 K个点。
这样做的最佳方法是什么？
这个Wiki页面在构建算法方面没有提供太多帮助。任何想法/方法都可以帮助人们。
最佳答案
解决方案1 创建大小为K的堆，并以最小距离 O(NLogK)复杂度收集点。
解决方案2 :
取N大小的数组，然后按距离排序。应该使用QuickSort(Hoare修改)。
作为答案，请先取得K分。
NlogN过于复杂，但有可能进行优化以逼近O(N)。
如果跳过不必要的子数组的排序。当您将数组除以2个子数组时，应仅取第K个索引所在的数组。
复杂度为:N + N / 2 + N / 4 + ... = O(N)。
解决方案3 :在结果数组中搜索第K个元素，然后减去所有要减去的点。存在 O(N)算法，类似于中值搜索。
注意:更好地使用sqr距离来避免sqrt操作，如果点具有整数坐标，它将更快。
作为面试答案最好使用解决方案2或3。
关于performance - 在二维平面中找到与P点最近的K个点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20398799/