Python solution a little bit different from 380

  • 0

    380 dic tracks one position in list, now dic tracks all the positions in list. Use self.count to track the valid length of list, so there is no need to shrink list.

    import random
    class RandomizedCollection(object):
        def __init__(self):
            Initialize your data structure here.
            self.dic = {}
            self.nums = []
            self.count = 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
            flag = False
            if val not in self.dic:
                self.dic[val] = set()
                flag = True
            # never shrink list, so count is true size
            if self.count == len(self.nums):
                self.nums[self.count] = val
            self.count += 1
            return flag
        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 not in self.dic:
                return False
            pos = self.dic[val].pop()
            if len(self.dic[val]) == 0:
                del self.dic[val]
            # fill with last num
            if pos != self.count - 1:
                self.nums[pos] = self.nums[self.count - 1]
                self.dic[self.nums[pos]].remove(self.count - 1)
            self.count -= 1
            return True
        def getRandom(self):
            Get a random element from the collection.
            :rtype: int
            return self.nums[random.randint(0, self.count - 1)]
    # 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()

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.