[解決済み] データ構造：挿入、削除、包含、ランダム要素の取得、すべてO(1)

質問

面接でこの問題を出されました。 あなたならどう答えますか？

以下の操作をO(1)時間で提供するデータ構造を設計せよ。

• 挿入
• 削除
• 含む
• ランダムな要素を取得する

どのように解決するのですか？

ハッシュテーブルHと配列Aからなるデータ構造を考える。ハッシュテーブルのキーはデータ構造中の要素であり、値は配列中の位置である。

1. insert(value)：値を配列に追加し、Aにおけるそのインデックスをiとし、H[value]=iとする。
2. remove(value)を実行します。Aの値を含むセルをAの最後の要素に置き換える。配列Aのインデックスmで最後の要素をdとし、iを削除する値の配列内のインデックスであるH[value]とする。A[i]=d, H[d]=i とし、配列のサイズを1つ小さくし、Hから値を削除する。
3. contains(value): H.contains(value)を返す。
4. getRandomElement(): let r=random(current size of A). return A[r].

配列は自動でサイズを大きくする必要があるので、要素を追加するのにO(1)の償却が必要になりますが、それでもいいんでしょう。