381. Insert Delete GetRandom O(1) Duplicates allowed (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class RandomizedCollection(object):

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

    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
        """
        result = True
        if self.h.get(val):
            result = False
        self.h[val] = self.h.get(val, []) + [len(self.arr)]
        self.arr.append(val)
        return result
        
    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 self.h.get(val):
            i = self.h[val][-1]
            self.h[self.arr[-1]][-1] = i
            self.h[self.arr[-1]].sort()
            self.arr[-1], self.arr[i] = self.arr[i], self.arr[-1]
            self.arr.pop()
            self.h[val].pop()
            if not self.h[val]:
                del self.h[val]
            return True
        return False

    def getRandom(self):
        """
        Get a random element from the collection.
        :rtype: int
        """
        return 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()