問題タブ [closest-points]

宿題があり、完全に行き詰まっています (レベル: 初級)。

ユーザーエントリと配列内のすべてのポイントから 3 つの最も近い距離を見つけるメソッドを作成する必要がありますが、ここで立ち往生しています。

メソッドは次のとおりです。 public static int[] troisPlusProches (int x, int y, int[] coordonneesHabitations) ここで、int x と int y はユーザー エントリであり、配列 int[] coordonneesHabitations は int[] coordonneesHabitations = {9, 30, です。 18、8、3、18、25、36}。したがって、点は (9,30)、(18,8)、(3,18)、および (25,36) です。

式を使用しました: distance = Math.sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2))) 距離を計算します。

そして今、ユーザーエントリから 3 つの最短距離を見つけて、それらの位置を新しい配列で返す必要があります。

したがって、ユーザー エントリが x=10 の場合、y=15 です。

最短距離は点 (3, 18) から 7.616、次は点 (18, 8) から 10.630、3 番目は点 (9, 30) から 15.033 です。この場合、メソッドは配列 int[] troisPlusProches = {3, 18, 18, 8, 9, 30} を返す必要があります。

やるべきことはわかっているのに、どうすればいいのかわからない…

これは多くの間違った試みの 1 つです。

O(nlgn) 時間で最も近いポイントのペアを見つける際に、ソート済みリストを 2 つのソート済みリストに分割するための疑似コード (CLRS 3rd ed pg 1043) は、O(n) 時間で実行されると言われています。

ただし、これは4行目が一定時間で実行されることを前提としていますが、これは信じがたいことです（バイナリツリーとして保存されている場合、O（lgn）時間で実行され、合計実行時間はO（nlgn）になります） .

Y はソートされた配列で、YL と YR は 2 つの新しいサブ配列です。PL はランダムな順序の Y のサブセットであり、YL は同じサブセットですが、ソートされた順序です。

私の推論のどこが間違っているのでしょうか?

クローゼット ペア アルゴリズムの n log^2 n 時間から n log n 時間に移行する方法を理解しようとしています。以下の部分を取得します（http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.htmlから）

1. セットを行 l で 2 つの等しいサイズの部分に分割し、各部分の最小距離を再帰的に計算します。
2. d を 2 つの最小距離の最小値とします。
3. l から d より遠くにある点を削除する
4. 残りのポイントを y 座標に従って並べ替えます
5. 残りの点を y 順にスキャンし、各点から 5 つの近傍点までの距離を計算します。
6. これらの距離のいずれかが d 未満の場合、d を更新します。

ステップ 4 は、O(n log n) 時間かかるソートであり、他のすべてのステップを支配します。これは、アルゴリズム全体が O(n log n) 時間を達成するために O(n) に減らす必要があるものです。 . そして、これは私が理解するのに苦労している部分です。著者が提案する

ステップ 1: セットを ... に分割し、各部分の距離を再帰的に計算し、各セットのポイントを y 座標でソートされた順序で返します。ステップ 4: 2 つのソート済みリストを O(n) 時間で 1 つのソート済みリストにマージします。

O(n log n) 時間かかる再帰ステップで、y 座標でポイントを並べ替える必要があります。どうすればこれを回避できますか? マージは O(n) ですが、まだどこかでソートする必要があります。