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) の時間と空間の複雑さを与えることです。