優先キューを使用して原点に最も近い K 個の点を見つけます

この問題では、指定された N 個の点から 2D 平面内の原点に最も近い K 個の点を見つけます。

標準のユークリッド距離公式を使用して、原点と指定された各点の間の距離を計算できます。その後、距離とともにポイントを配列に保存し、距離に基づいて配列を並べ替えて、上位 K 個のポイントを取得します。

ただし、優先キューを使用して、原点からの距離に基づいて 2D ポイントを保存することもできます。その後、キューから K 回デキューできます。

問題文- 2 次元平面上に N 個の点が与えられます。平面の原点に最も近い K 点を見つける必要があります。

注意 - ユークリッド距離は、原点と平面上の特定の点の間の距離として扱います。

- 各点から原点までのユークリッド距離を示します。

(2, −2) −> sqrt(8)

(−5, 1) −> sqrt(26)

(2, 1) -> sqrt(5)
(0, 3) −> sqrt(9)
(6, 0) -> sqrt(36)
(5, 5) -> sqrt(50)
(4, 9) -> sqrt(97)
したがって、最も近い 4 つの点は {2,1} {2,−2} {0,3} {−5,1} となります。
• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- すべての点から原点までの距離は同じです。したがって、任意の 2 点を出力として印刷できます。
• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- K は指定された点に等しい。したがって、すべての点を出力する必要があります。

方法 1

このメソッドでは、sort() メソッドを使用して配列をソートします。さらに、コンパレータ関数を使用して、原点からの距離に基づいてポイントを並べ替えます。その後、ソートされた配列の最初の K 要素を出力します。 ＃＃＃アルゴリズム＃＃＃

- sort() メソッドを使用してリストを並べ替え、distComparator() 関数を 3 番目のパラメーターとして渡します。

- 指定された点の距離を比較する distComparator() 関数を定義します。この関数はパラメータとして p と q のペアを取ります。

- 点 p から原点までの距離を取得し、dist_p に保存します。

- 点 q から原点までの距離を dist_q 変数に保存します。

- dist_p が dist_q より小さい場合、true を返します。それ以外の場合は false を返します。

- 配列を反復処理し、配列の最初の K 点を出力します。

時間計算量 - 配列のソートの時間計算量は O(NlogN) です。

空間複雑度 - 配列のソートに O(N)。

方法 2 この方法では、優先キューを使用してポイントを挿入します。さらに、比較関数と優先キューを使用して、原点からの最短距離に基づいてポイントを保存します。

ステップ 1 - K 個の最近接点を保存するために「res_points」リストを定義します。

ステップ 2- 優先キューを定義します。ここで、「pair

以上が優先キューを使用して原点に最も近い K 個の点を見つけますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。