380. Insert Delete GetRandom O(1)

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

感觉这是道高频题，之前pivotal面过，现在亚麻又面了，注意，add delete的number可以有duplicate还有这个O(1)的操作很有迷惑性，让我直接先放弃了用list因为想到list都会想到O(N)

但是看了解法，还是用了list 来record nums, pos 因为这样的getRandom 是最直接的

len(x) time complexity is O(1) here

import random
class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.pos = dict()
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val not in self.pos:
            self.nums.append(val)
            self.pos[val] = len(self.nums)-1
            return True
        return False
        

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.pos:
            idx = self.pos[val]
            last = self.nums[-1]
            # swap the last one with removal one
            self.nums[-1] = val
            self.nums[idx] = last
            self.pos[last] = idx
            #remove the last one
            self.nums.pop()
            del self.pos[val]
            return True
        return False
    

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        randIndex = random.randint(0,len(self.nums)-1)
        return self.nums[randIndex]