Matsushita's Blog

Insert Delete GetRandom O(1)

問題

通常のハッシュテーブルの機能に加えて、テーブル内の要素をランダムで取得するメソッドが実装されたデータ構造をデザインする問題。 全ての操作はO(1)で行う必要がある。

leetcode.com

解法

HashMapとArrayListを用いることで解くことができる。問題はノードを削除する時だが、ArrayListからIndexを指定して要素を削除する場合、削除した分だけ要素をシフトさせる必要があるため、O(1)を実現できない。そこで以下の方法を取る。

  1. 削除したい要素のIndexを取得
  2. ArrayList内で最後の要素とIndexの要素をSwap
  3. ArrayListの最後の要素を削除(シフトさせる必要が無くなる)

ソースコード