優先キューを使用して原点に最も近い K 個の点を見つけます
- WBOY転載
- 2023-09-14 21:01:111281ブラウズ
この問題では、指定された N 個の点から 2D 平面内の原点に最も近い K 個の点を見つけます。
標準のユークリッド距離公式を使用して、原点と指定された各点の間の距離を計算できます。その後、距離とともにポイントを配列に保存し、距離に基づいて配列を並べ替えて、上位 K 個のポイントを取得します。
ただし、優先キューを使用して、原点からの距離に基づいて 2D ポイントを保存することもできます。その後、キューから K 回デキューできます。
問題文- 2 次元平面上に N 個の点が与えられます。平面の原点に最も近い K 点を見つける必要があります。
注意 - ユークリッド距離は、原点と平面上の特定の点の間の距離として扱います。
＃＃＃例＃＃＃ ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー 説明- 各点から原点までのユークリッド距離を示します。
(2, −2) −> sqrt(8)
(−5, 1) −> sqrt(26)
- (2, 1) -> sqrt(5)
-
- ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー 説明 - すべての点から原点までの距離は同じです。したがって、任意の 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- 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 サイトの他の関連記事を参照してください。