12

これはインタビューの質問です。整数を格納し、2 つの操作を提供するクラスを設計します。

無効な挿入 (int k)
int getMedian()

insertO（logN）とO（logN）を取るようにBSTを使用できると思いますgetMedian（getMedian各ノードの左/右の子の数を追加する必要があるため）。

これが最も効率的な解決策であり、これ以上の解決策はないのではないかと思います。

4

4 に答える 4

27

Leftと呼ばれる 2 つのヒープを使用できますRight。
LeftですMax-Heap。
RightですMin-Heap。
挿入は次のように行われます。

  • 新しい要素xが のルートよりも小さい場合はLeft、 に挿入xしLeftます。
  • そうでなければ、に挿入xしRightます。
  • LeftAfter insertの要素数が の要素数から 1 より大きい場合、RightExtract-Max を呼び出してに挿入LeftしRightます。
  • それ以外の場合、挿入後Rightの要素数が の要素数より多い場合は、LeftExtract-Min を呼び出してRightに挿入しLeftます。

中央値は常に の根ですLeft。

したがって、挿入は時間内O(lg n)に行われ、中央値の取得は時間内に行われO(1)ます。

于 2012-07-08T18:07:46.857 に答える
5

2 つのヒープを含むソリューションについては、このスタック オーバーフローの質問を参照してください。

于 2012-07-06T15:46:26.640 に答える
1

O < O(log(n) ) 配列を使用すると、getMedian はサイズの半分でインデックスを取得し、O(1) になりますよね? log(n) + log(n) よりもうまくいくように思えます。

さらに、もう少し柔軟にすることで、入力のプロパティに応じてソートアルゴリズムを変更することでパフォーマンスを向上させることができます (入力がほとんどソートされているかどうか...)。

私はほとんどコンピューター サイエンスを独学で学んでいますが、それが私のやり方です。

于 2012-07-06T11:46:46.667 に答える
1

自己均衡ツリーも考えられます。ツリーが完全にバランスが取れている場合、ルート ノードは中央値です。たとえば、ツリーの一方の端が 1 レベル深いとします。次に、正しい中央値を選択するために、より深い側にいくつのノードがあるかを知る必要があります.

于 2012-07-06T14:28:50.203 に答える