優先キューを使用して原点に最も近い 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 要素を出力します。 ＃＃＃アルゴリズム＃＃＃

ステップ 1

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

ステップ 2

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

ステップ 2.1

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

ステップ 2.2

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

ステップ 2.3

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

ステップ 3

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

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

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

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

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

＃＃＃アルゴリズム＃＃＃

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

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

」は、優先キューを使用して整数ペアを格納することを意味します。 「vector>」は、ベクトルを使用してペアを保存することを意味します。さらに、優先キューを備えた「cmp」関数を使用しました。 ステップ 3

- 2 点と原点の間のユークリッド距離を比較する cmp() 関数を定義します。

ステップ 3.1

- 点 a から原点までの距離が点 b から原点までの距離より大きいことに基づいてブール値を返します。

ステップ 4

- 配列の各要素を優先キューに挿入します。

ステップ 5

- 最初の K 要素をキューからポップし、res_points リストに保存します。

ステップ 6

- ポイントの res_points リストを返します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(N*logN) N 個の要素を優先キューに挿入します。ここで、N はポイントの総数です。

スペースの複雑さ - 優先キューにポイントを保存するには O(N)。

プライオリティキューはヒープデータ構造を使用します。したがって、要素の挿入と削除には O(logN) 時間しかかかりません。どちらの方法でも同じメモリと時間が必要です。ただし、2 番目の方法はヒープ データ構造を使用するため、より効率的です。

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