algorithm - 最接近原点的二维坐标

Question

我正在看下面的面试题:

Given 2d coordinates , find the k points which are closest to the origin. Propose a data structure for storing the points and the method to get the k points. Also point out the complexity of the code.

我想出的解决方案是将二维点保存在一个数组中。对于前 k 个点，找出每个点到原点的距离并构建一个最大堆。对于剩余的点，计算与原点的距离，比如 dist。如果 dist 大于堆的最顶层元素，则将堆的最顶层元素更改为 dist 并运行 heapify() 过程。

构建堆需要O(k)，heapify()过程需要O((n-k)log k)，因此总复杂度 = O(n log k)。

谁能建议一个更好的数据结构和/或方法，而且效率也可能更高？

编辑

其他一些数据结构在这里会有用吗？

Answer 1

您要找的是partial sorting .

我认为最好的方法是将所有内容放入未排序的数组中，然后使用修改后的就地快速排序忽略索引完全高于或完全低于 k 的分区，并使用距离来源作为您的比较。

来自上面维基百科文章的伪代码:

function quickfindFirstK(list, left, right, k)
     if right > left
         select pivotIndex between left and right
         pivotNewIndex := partition(list, left, right, pivotIndex)
         if pivotNewIndex > left + k  // new condition
             quickfindFirstK(list, left, pivotNewIndex-1, k)
         if pivotNewIndex < left + k
             quickfindFirstK(list, pivotNewIndex+1, right, k+left-pivotNewIndex-1)

执行后，这会将最小的 k 项留在前 k 位置，但不按顺序排列。