python solution


  • 0
    A

    '''
    import random
    class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.vals=[]
        self.pos={}# use dictionary to keep the index of the value
        
    
    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 not in self.pos:
            self.vals.append(val)
            self.pos[val]=len(self.vals)-1
            return True
        return False
        
    
    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 we want to remove value val, we find its index, write the last value in the list to this position, then pop the last value

        if val in self.pos:
            self.pos[self.vals[-1]]=self.pos[val]
            self.vals[self.pos[val]]=self.vals[-1]
            self.vals.pop()
            del self.pos[val]
            return True
        return False
        
        
    
    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return self.vals[random.randint(0,len(self.vals)-1)]
    

    '''


Log in to reply
 

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