1

タスクは、次のメソッドを使用してJavaでキューを実装することです。

  1. enqueue//キューに要素を追加します
  2. dequeue//キューから要素を削除します
  3. peekMedian//中央値を検索
  4. peekMinimum//最小値を見つける
  5. peakMaximum//最大値を見つける
  6. サイズ//サイズを取得

すべてのメソッドが同等の頻度で呼び出されると想定します。タスクは、最速の実装を行うことです。

私の現在のアプローチ：キューに加えて、ソートされた配列を維持するため、エンキューとデキューはO（logn）かかり、peekMedian、peekMaximum、peekMinimumはすべてO（1）時間かかります。

すべてのメソッドが同じ頻度で呼び出されると仮定して、より高速なメソッドを提案してください。

4

2 に答える 2

4

さて、あなたは近くにいます-しかし、ソートされた配列からの挿入/削除はO(n)（確率1/2で、挿入された要素は配列の前半にあり、右にシフトする必要があるため）、まだ何かが欠けています以下のすべての要素、およびこれらの少なくともn / 2があるため、この操作の全体的な複雑さはO(n)平均+最悪の場合です）

ただし、ソートされたDSをスキップリスト/バランスの取れたBSTに切り替えると、O(logn)挿入/削除とO(1)最小/最大/中央値/サイズ（キャッシュあり）が表示されます。

編集：

O(logN)挿入の場合は（にを減らさない限りpeekMedian()）Omega(logN)、より適切に並べ替えることができるため、より適切に並べ替えることはできませんO(NlogN)。

まず、中央値は、挿入する「高」要素ごとに1つの要素を右に移動することに注意してください（ここでは、高は> =現在の最大値を意味します）。
したがって、繰り返し実行することにより、次のようになります。

while peekMedian() != MAX:
   peekMedian()
   insert(MAX)
   insert(MAX)

ソートされた配列の「上位」半分を見つけることができます。
同じアプローチを使用するとinsert(MIN)、配列の下半分を取得できます。

o(logN)（小さなo表記、Theta(logN)挿入とO（1）よりも優れていると仮定すると、より優れpeekMedian()たソートが得られますO(NlogN)が、ソートにはOmega(NlogN)問題があります。
=> <=

したがって、中央値はまだですが、insert()それよりも優れていることはありません。O(logN)O(1)

QED

EDIT2：挿入の中央値を変更します：

挿入前のツリーサイズが2n+1（奇数）の場合、古い中央値はインデックスn + 1にあり、新しい中央値は同じインデックス（n + 1）にあるため、要素が古い中央値の前に追加された場合-最後の中央値の前のノードを取得する必要があります-それが新しい中央値です。その後に追加された場合は、何もしないでください。古い中央値も新しい中央値になります。

リストが偶数（2n要素）の場合、挿入後にインデックスを増やす必要があります（nからn + 1に）。したがって、新しい要素が中央値の前に追加された場合は何もしません。古い要素の後に追加された場合は何もしません。中央値、古い中央値から次のノードとして新しい中央値を設定する必要があります。

注：ここでは、次のノードと前のノードはキーに従って続くノードであり、インデックスはノードの「場所」を意味します（最小が最初で最大が最後）。
私は挿入のためにそれを行う方法を説明しただけで、同じ考えが削除にも当てはまります。

于 2013-01-16T16:39:50.557 に答える
0

より単純でおそらくより良い解決策があります。（すでに説明したように、ソートされた配列は両方のO（n）をエンキューおよびデキューしますが、これはあまり良くありません。）

キューに加えて、2つのソートされたセットを更新します。Javaライブラリは、バランスの取れた検索ツリーであるSortedSetなどを提供します。「ローセット」は、最初の上限（n / 2）要素をソートされた順序で格納します。2番目の「ハイセット」には最後のフロア（n / 2）があります。

注意：重複が許可されている場合は、通常のJavaソートセットの代わりに、GoogleのTreeMultisetなどを使用する必要があります。

キューに入れるには、キューと正しいセットに追加するだけです。必要に応じて、1つの要素を移動して、セット間のバランスを再確立します。つまり、低いセットの最大要素を上のセットに移動するか、高いセットの最小要素を低いセットに移動します。デキューには、同じリバランス操作が必要です。

nが奇数の場合の中央値を見つけることは、低いセットの最大要素を調べることです。nが偶数の場合、低いセットで最大要素を見つけ、高いセットで最小要素を見つけて、それらを平均します。

ネイティブJavaソートセット実装（バランスツリー）では、これはすべての操作でO（log n）になります。コーディングは非常に簡単です。約60行。

低セットと高セットに独自のふるい分けヒープを実装する場合、中央値の検索操作用にO（1）があり、他のすべての操作はO（log n）のままです。

続けて、ローセットとハイセットに独自のフィボナッチヒープを実装する場合は、O（1）インサートも必要になります。

于 2013-01-17T03:23:00.513 に答える