Insert Delete GetRandom O(1)

有随机读取功能的数据结构，首先一定要用到random模块去取值，这里用了一个哈希表解决了问题，但是实际上是用了一个哈希表和一个list，我们只是把list省去而直接利用哈希表的keys函数了

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.store = {}
        self.count = 0

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.store:
            return False
        self.store[val] = 1
        self.count += 1
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.store:
            self.store.pop(val)
            self.count -= 1
            return True
        return False

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        seed = random.randint(0, self.count - 1)
        return self.store.keys()[seed]

Insert Delete GetRandom O(1) - Duplicates allowed

此题思考难度很小，哈希表嵌套哈希表来查重记下标就可以了，再加上一个list来供getrandom使用，最后维护一个长度变量，但是因为数据结构使用的多，之间的一致性保持上很复杂，这里有几个很大的坑，首先是当一个key的下标集合为空时，我们要把它从字典中删除，另外我们有可能在某次删除某个值时从它对应集合里弹出的下标就是数组的最后一个下标，如果此种情况，我们必须直接从list里面弹出值，不做额外处理了，如果弹出下标不是最后一个，为了保持函数的O(1)特性，我们必须找到最后一位的数，将里面的最后一位下标删去，同时将刚开始弹出的下标加进最后这个数的下标，最后再将list里面两个数位置互换再通过pop弹出，这也是这道题最复杂的操作了

class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.checker = collections.defaultdict(set)
        self.collection = []
        self.length = 0

    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.collection.append(val)
        self.length += 1
        if val in self.checker:    
            self.checker[val].add(self.length - 1)
            return False
        self.checker[val].add(self.length - 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
        """
        tmp = self.checker.get(val, -1)
        if tmp == -1:
            return False

        index = self.checker[val].pop()
        if not self.checker[val]:
            self.checker.pop(val)

        if index != self.length - 1:
            self.checker[self.collection[self.length - 1]].discard(self.length - 1)
            self.checker[self.collection[self.length - 1]].add(index)
            self.collection[index], self.collection[self.length - 1] = self.collection[self.length - 1], self.collection[index]

        self.collection.pop()
        self.length -= 1
        return True

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