380. Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/

solution

class RandomizedSet:
    def __init__(self):
        self.list = []
        self.data_map = {}

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

    def remove(self, val: int) -> bool:
        if val not in self.data_map:
            return False
        last_element = self.list[-1]
        index_of_element = self.data_map[val]

        self.data_map[last_element] = index_of_element
        self.list[index_of_element] = last_element

        self.list[-1] = val
        self.list.pop()
        self.data_map.pop(val)
        return True

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

时间复杂度：O() 空间复杂度：O()

follow up

381. Insert Delete GetRandom O(1) - Duplicates allowed