python solution using two maps / or map + list, inline explanation

  • 2
    # bijective maps.
    # when remove an element , use the last element in the map to fill the hole left by the removed element.
    import random
    class RandomizedSet(object):
        def __init__(self):
            self.key_val = {}  #key from 1 to self.size; val is the inserted val. can use list here instead.
            self.val_key = {}  #reversed map of the above. 
            self.size = 0
        def insert(self, val):
            if val in self.val_key:
                return False
                self.size += 1
                self.val_key[val] = self.size
                self.key_val[self.size] = val
                return True
        def remove(self, val):
            if val not in self.val_key:
                return False
                # use the last element to fill the hole left by the removed element
                key = self.val_key[val]
                last = self.key_val[self.size]
                self.key_val[key] = last
                self.val_key[last] = key
                del self.val_key[val]
                del self.key_val[self.size]
                self.size -= 1
                return True
        def getRandom(self):
            i = random.randrange(1, self.size+1)
            return self.key_val[i]

  • 0

    Hi, I used similar implementation as yours. However it failed at the last test case where getRandom() retrieves different values against the answer. Did you get your solution accepted?

Log in to reply

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