Python solution a little bit different from 380


  • 0
    P

    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
            self.dic[val].add(self.count)
            # never shrink list, so count is true size
            if self.count == len(self.nums):
                self.nums.append(val)
            else:
                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.dic[self.nums[pos]].add(pos)
            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.