14

0(1) 時間の複雑さでいつでもキューから最大要素と最小要素を取得するにはどうすればよいですか? 以前は Collections.max と min を使用して要素を見つけていましたが、それは 0(n) になります。

4

7 に答える 7

70

キューのように機能する構造が存在しますが、最小/最大値を一定時間で取得できます。実際には厳密には一定ではなく、一定時間償却されます (ご想像のとおり、最小/最大キューと呼ばれます)。これを実装するには、2 つのスタックを使用する方法と、キューと両端キューを使用する方法の 2 つがあります。

Deque の実装は、次のようにはなりません (言語に依存しません)。

そのため、最大要素の両端キューがあり、先頭にあるのは目的の最大値であり、標準のキューです。

プッシュ操作

  1. キューが空の場合は、キューと両端キューの両方に要素をプッシュするだけです。
  2. キューが空でない場合は、要素をキューにプッシュし、両端キューの後ろから、現在プッシュしている要素よりも厳密に小さいすべての要素を削除します (プッシュされた要素が大きいため、それらはおそらく最大ではありません)長くキューに残ります) そして、現在の要素を両端キューの後ろにプッシュします

削除操作

  1. deque の先頭が queue の先頭と等しい場合は、両方をポップします (先頭から deque します)。
  2. 両端キューの先頭がキューの先頭と等しくない場合は、キューだけをポップします。ポップされた要素は確かに最大のものではありません。

最大を得る

  1. これは両端キューの最初の要素にすぎません。

（なぜそれが機能するのかを明確にするために多くの引数を追加する必要がありますが、以下に示す2番目のバージョンがこの必要性に対する答えかもしれません）

スタックの実装は非常に似ています。実装には少し時間がかかるかもしれませんが、おそらく理解しやすいと思います。最初に注意すべきことは、最大要素をスタックに格納するのは簡単だということです。2 番目の部分は、初めて見た場合は少しトリッキーかもしれませんが、2 つのスタックを使用してキューを実装するのは非常に簡単であるということです。ここで見つけることができます - How to implement a queue using two stacks? . そして、それは基本的にそれです-両方のスタックの最大要素を取得できれば、キュー全体の最大要素を取得できます(より正式な引数が必要な場合は、最大値を取ることは連想またはそのようなものですが、私はあなたがしないに違いない't、それは本当に明らかです）。

最小バージョンは類推的に行われます。

O(nlogn) 時間でセット (またはそのようなもの) を使用してすべてを実行することもできますが、O(n) の定数は非常に小さく、はるかに高速でありながら実装が簡単であるため、無意味です。

最初のバージョンの面白くない部分:

少しお役に立てば幸いです。そして、それが間違ったことを言っていないことを願っています。必要に応じて、C++/C で簡単な実装を提供できます。このタイプの投稿は初めてなので、フォームに関するフィードバックをいただければ幸いです :) (英語は私の母国語ではありません)。また、正確さについての確認も素晴らしいでしょう。

編集：この回答でいくつかのポイントが得られたので、少しクリーンアップする義務があると感じ、少し拡張しました。

于 2013-01-02T22:26:21.310 に答える
9

最小/最大操作でO（1）を取得する方法は2つしかありません。

  • 構造がソートされていて、最大/最小がどこにあるかがわかっている場合
  • 構造がソートされておらず、挿入のみが許可されている場合：アイテムを挿入するたびに最小/最大を再計算し、値を個別に保存できます
  • 構造がソートされておらず、挿入と削除が許可されている場合：複数のコレクションを使用しない限り、O（n）よりも優れているとは思いません（ただし、そのソリューションは要素の削除をサポートしておらず、ヘッド/テールのみをサポートしています要素。これはキューの場合に当てはまります）。
于 2012-08-21T12:05:51.937 に答える
0

PriorityQueueの機能を実装しようとしているのではないかと思います。これは、最小値を取得するためにO（log N）するソートされたキューです。キューには一方の端しかないので、なぜ最大の値にしたいのかわかりません。

于 2012-08-21T12:06:30.083 に答える
0

これは実際にはキューではありませんが、Min-Max Heap を実装できます。

http://en.wikipedia.org/wiki/Min-max_heap

基本的に、偶数レベルで最大ヒープ プロパティ、奇数レベルで最小ヒープ プロパティを持つヒープです。

O(1) MIN() と O(1) MAX() の両方の操作があります。ただし、反復するのはかなり難しいですが、機能し、要件を満たしています。

于 2013-01-02T22:57:06.613 に答える
-1

それぞれ最小値と最大値のインデックス位置をデータ構造に格納する 2 つのフィールドminIndexとmaxIndexを格納します。

新しい要素がキューに追加されたら、次の 2 点を確認してください。

  1. 要素は、minIndex位置で現在の最小要素よりも小さいです。その場合、挿入後にminIndexの値を更新します。
  2. この要素は、 maxIndexの位置にある現在の最大要素よりも大きく、それに応じて参照を更新します。

これにより、現在の最小値と最大値の O(1) 漸近線が得られます。

于 2012-08-21T12:11:43.200 に答える