4

n個のペアごとに異なる要素の配列と1<=k<=nの数kがあります。

ここで、数値配列の中央値との絶対差が最小になるように数値を計算するアルゴリズムを探していますk。線形の複雑さが必要です（O(n)）。

私のアプローチ：

私は中央値を見つけます：

  • 番号を並べ替えます
  • 真ん中の要素を取得するか、要素の数が同じである場合は、真ん中とラウンドの2つの要素の平均を取得します。

その後：

  • 私はすべての数値を取り、中央値からの絶対距離を見つけます。これらの結果を別の配列に保存します
  • 新しく取得した配列を並べ替えます。
  • 結果配列の最初のk個の要素を取得して完了です。

私の解決策がO(n)正しいかどうか、また私がこの考えに正しいかどうかもわかりません。誰かがそれを確認できますか？誰かがO（n）でそれを解決する方法を教えてもらえますか？

4

1 に答える 1

9

次のように問題を解決できます。

nth_element アルゴリズムO(n)を使用して、wgで中央値を見つけることができます。O(n)

それぞれをペアで置き換えて、すべての要素をループします: <the absolute difference to the median>, <element's value>。もう一度 nth_element をn=で実行しますk。kこのアルゴリズムを適用すると、絶対差の最小要素が最初に新しい配列に含まれることが保証されます。あなたは彼らのインデックスを取り、DONE！

一方、あなたのアルゴリズムはソートを使用しており、これによりO(nlogn).

編集: 要求された例:

配列を とします[14, 6, 7, 8, 10, 13, 21, 16, 23]。

  • 中央値を見つけるためのステップの後、次のように並べ替えられます。[8, 7, 9, 10, 13, 16, 23, 14, 21]配列はソートされていませんが、中央値 (13) はちょうど真ん中にあります。
  • では、あなたを混乱させたペア置換を行いましょう: ペアの新しい配列を作成します: [<abs(14-13), 14>, <abs(6-13), 6>, <abs(7-13), 7>, <abs(8-13), 8>, <abs(10-13), 10>, <abs(13-13), 13>, <abs(21-13), 21>, <abs(16-13), 16>, <abs(23-13), 23>. したがって、配列を取得します。[<1, 14>, <7, 6>, <6, 7>, <5, 8>, <3, 10>, <0, 13>, <8, 21>, <3, 16>, <10, 23>
  • 例えばk​​4 の場合、もう一度 nth_element (比較のために各ペアの最初の要素を使用) を作成し、以下を取得します。[<1, 14>, <3, 16>, <0, 13>, <3, 10>, <8, 21>, <7, 6>, <10, 23>, <6, 7>, <5, 8>]したがって、検索する数値は、最初の 4 つのペアの 2 番目の要素です: 14、16、13および10
于 2013-01-13T11:24:02.077 に答える