380. Insert Delete GetRandom O(1)

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

solution

要求: each function works in average O(1) time complexity

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()

class RandomizedSet:
    def __init__(self):
        self.set = set()        

    def insert(self, val: int) -> bool:
        if val in self.set:
            return False
        else:
            self.set.add(val)
            return True        

    def remove(self, val: int) -> bool:
        if val in self.set:
            self.set.remove(val)
            return True
        return False        

    def getRandom(self) -> int:
        # set无序，转为list需要创建index，时间复杂度O(n)
        return random.choice(list(self.set))

follow up

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

# follow1: delete function with a twist that there can be duplicates as well
# follow2: Modify the map such that each unique element has equal probability of being returned. Ex: If values in map are [5,5,6,5,5] both 5 and 6 have 50% probability of being returned.