3

これはほぼ 3 年前に私に尋ねられたインタビューの質問であり、私はしばらく前にこれについて熟考していました.

次の操作をサポートするデータ構造を設計します: insert_back()、remove_front()、および find_mode()。最高の複雑さが必要です。

私が考えることができる最良の解決策は、挿入と削除に O(logn) 、モードに O(1) でした。これが私がそれを解決した方法です。挿入および削除される要素を処理するためのキュー DS を保持します。また、最大ヒープ順の配列とハッシュ テーブルを保持します。ハッシュテーブルには、整数キーと、その要素のヒープ配列の場所へのインデックスが含まれています。ヒープ配列には順序付けられたペア (カウント、要素) が含まれ、カウント プロパティで順序付けられます。

Insertion : 要素をキューに挿入します。ハッシュテーブルからヒープ配列インデックスの場所を見つけます。存在しない場合は、要素をヒープに追加し、上向きにヒープ化します。次に、最終的な場所をハッシュテーブルに追加します。その場所のカウントを増やし、必要に応じて上向きまたは下向きにヒープ化し、ヒープ プロパティを復元します。

削除 : キューの先頭から要素を削除します。ハッシュ テーブルから、ヒープ配列インデックス内の場所を見つけます。ヒープ内のカウントを減らし、必要に応じて上向きまたは下向きに再ヒープして、ヒープ プロパティを復元します。

検索モード: 配列ヒープ (getMax()) の先頭にある要素がモードを示します。

誰かがより良いものを提案してください。考えられる唯一の最適化は、フィボナッチ ヒープを使用することでしたが、それがこの問題に適しているかどうかはわかりません。

4

1 に答える 1

2

O(1)すべての操作に対して解決策があると思います。

両端キューと 2 つのハッシュテーブルが必要です。

最初のものはリンクされたハッシュテーブルで、それぞれにその、要素をカウント順にelement格納し、要素をカウント順に格納します。次に、そのハッシュテーブル内の次の要素と前の要素のエントリを一定時間で見ることができます。このハッシュテーブルでは、カウントが最大の要素も保持および更新します。( )countnextpreviouselement -> count, next_element, previous_element

要素の数ごとに 2 番目のハッシュテーブルに、その数の要素を最初のハッシュテーブルの範囲の最初と最後に格納します。このハッシュテーブルのサイズは より小さいことに注意してくださいn(それO(sqrt(n))は だと思います)。( count -> (first_element, last_element))

基本的に、deque に要素を追加したり要素を削除したりする場合、その要素nextとprevious要素を分析することで最初のハッシュテーブルの新しい位置を見つけ、一定時間で 2 番目のハッシュテーブルの古いカウントと新しいカウントの値を見つけることができます。リンクされたリストのアルゴリズムを使用して、最初のハッシュテーブルの要素を一定時間で削除および追加できます。2番目のハッシュテーブルと最大カウントを持つ要素も一定時間で更新できます。

必要に応じて疑似コードを書いてみますが、特殊なケースが多く非常に複雑なようです。

于 2013-09-27T16:02:16.060 に答える