8.21 - hard - 76

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

设计数据结构， 这种题目还是挺巧妙的

class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.h = {}
        self.arr = []
        

    def insert(self, val):
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        self.arr.append(val)
        if val in self.h:
            self.h[val].add(len(self.arr) - 1)
            return False
        else:
            self.h[val] = set([len(self.arr) - 1])
            return True

    def remove(self, val):
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.h and self.h[val]:
            out, ins = self.h[val].pop(), self.arr[-1] # val的一个index，和最后一个值
            self.arr[out] = ins # 把那个index的值设置为arr的最后一个值
            if self.h[ins]: # 如果arr的最后一个值存在于h里
                self.h[ins].add(out)
                self.h[ins].discard(len(self.arr) - 1)
            self.arr.pop() #删掉arr的最后一个值
            return True
        return False 
        

    def getRandom(self):
        """
        Get a random element from the collection.
        :rtype: int
        """
        return random.choice(self.arr)

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