問題の振り返り

LeetCode の Top Interview 150 について「380. Insert Delete GetRandom O(1)」の解答例から学んだことを共有したいと思います。

問題の概要

この問題はRamdamizedクラスの中身について、初期化、挿入、削除、ランダム取得の機能を書き加えるという内容でした。

参考にした解答例

python


class RandomizedSet:

    def __init__(self):
        self.data_map = {}
        self.data = []

    def insert(self, val: int) -> bool:
        if val in self.data_map:
            return False
        
        self.data_map[val] = len(self.data)

        self.data.append(val)

        return True

    def remove(self, val: int) -> bool:
        if not val in self.data_map:
            return False
        
        last_elem_in_list = self.data[-1]
        index_of_elem_to_remove = self.data_map[val]

        self.data_map[last_elem_in_list] = index_of_elem_to_remove
        self.data[index_of_elem_to_remove] = last_elem_in_list

        self.data.pop()

        self.data_map.pop(val)
        return True

    def getRandom(self) -> int:
        return random.choice(self.data)


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

メイン

この問題を通して「なるほどな～」と思ったのは、処理時間をO(1)で収めるには辞書型とリスト型の両方を使わないといけないところです。辞書型とリスト型では計算量がO(1)で済む処理が異なり、これらをうまく組み合わせる必要があります。

たとえば、辞書型だけでランダムに要素を取得しようとすると次のような処理が必要です。

1 . 辞書型のキーをリストに変換する。
2 . リストからランダムなインデックスを選択する。
3 . 選択したインデックスに対応するキーをリストから取得する。
4 . 取得したキーに対応する値を辞書型から取得する。

この方法ではキーをリストに変換する処理時間O(n)の時間がかかり、getRandomをO(1)時間で実行することができません。

このような問題を回避するために辞書型とリスト型を使い分けることになります。

removeの箇所について少し解説

次のような考え方をすると理解しやすいです。

1 . リスト型の末尾を消すときは処理時間がO(1)になる
2 . 消したい要素はリストの末尾に持ってくればいい
3 . 言い換えると、元からリストの最後にあった要素を消したい要素の位置に上書きし、2個存在する要素のうちリスト末尾にある方を消せばよい
4 . この処理に応じて辞書型では、元からリスト末尾にあった要素のインデックスを変える必要がある

おわりに

今回の問題を通して以前よりも「それぞれの計算量を考えることは重要だ」と思うようになりました。今後もLeetCodeの解答例について解説などを共有していこうと思います。