java - JAVA 2D在2D平面中找到离原点最近的K个点

Question

给定一个包含 N 个点的数组，在 2D 平面中找到离原点最近的 K 个点。您可以假设 K 远小于 N 并且 N 非常大。

这是我到目前为止所拥有的：

   public class OriginQuestion {

     public static class Point {

     public double x;

    public double y;

 } 
  public static Point[] closestk( Point  myList[], int k ) {}
    for(int i=0;i<myList.length;i++){

    }

  }

帮助表示赞赏

Answer 1

这个问题是最近邻搜索问题的一个变体。最简单的解决方案是计算从原点到所有 N 个点的距离，然后使用例如快速选择算法找到最近的 K ，给出 O(n) 的时间和空间复杂度。

Answer 2

这个问题可以使用堆来解决。我们可以从创建一个大小为 k 的最大堆开始，然后开始向它添加点。完成后将 K 个点添加到我们的堆中。

现在，如果第 (K+1) 个点的距离低于最大堆根，我们删除根并将这个第 (K+1) 个点添加到我们的最大堆中。

在我们处理完所有 N 个点后，我们的堆将为我们提供解决方案。最坏情况的复杂度应该是 N(log K)，因为我们将对 N 个数字执行此操作，并且需要 log K 操作来移动堆中的节点。