Python solution with detailed explanation


  • 0
    G

    Solution

    Insert Delete GetRandom O(1) - Duplicates allowed

    1. This is an extension of the related problem. Instead of hash-map of value to index, we use a hash-map of value to set of indices.
    2. Insertion is easy - always add to the end.
    3. Removal is tricky as usual.
    • Test if value is in this set or not
    • Pop any index from the set of indices for this value
    • If the index is the last element, pop from nums array and return
    • Otherwise swap with the last element.
    • Then you need to fix the hash-map:
      last_number = self.nums[-1] # Get the last number
      self.nums[idx], self.nums[-1] = last_number, val # Swap with the last number
      self.hmap[last_number].remove(len(self.nums)-1) # Remove the last index for last_number
      self.hmap[last_number].add(idx) # Add idx to the set for last_number
      self.nums.pop()
    from random import randint
    class RandomizedCollection(object):
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.nums = []
            self.hmap = {}
            return        
    
        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
            """
            if (val not in self.hmap):
                self.hmap[val] = set([])
            self.nums.append(val)
            self.hmap[val].add(len(self.nums)-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 not in self.hmap or not self.hmap[val]:
                return False
            else:
                idx = self.hmap[val].pop()
                if idx == len(self.nums)-1:
                    self.nums.pop()
                else:
                    last_number = self.nums[-1]
                    self.nums[idx], self.nums[-1] = last_number, val
                    self.hmap[last_number].remove(len(self.nums)-1)
                    self.hmap[last_number].add(idx)
                    self.nums.pop()
                return True        
    
        def getRandom(self):
            """
            Get a random element from the collection.
            :rtype: int
            """
            if len(self.nums) != 0:
                return self.nums[randint(0, len(self.nums)-1)]
    

Log in to reply
 

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