Python solution (188ms) with time complexity notations for each step


  • 0
    P

    """

    from random import randint
    class RandomizedSet(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.vals = list()
            self.locs = dict()
    
        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 in self.locs: # O(1)
                return False
            else:
                self.vals.append(val)  # O(1)
                self.locs[val] = len(self.vals) - 1  # O(1)
                return True
    
        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 val in self.locs: # O(1)
                lastval = self.vals[-1] # O(1)
                if lastval != val:
                    pos = self.locs[val] # O(1)
                    self.vals[pos], self.vals[-1] = self.vals[-1], self.vals[pos] # O(1)
                    self.locs[lastval] = pos # O(1)
                self.vals.pop(-1) # O(1)
                self.locs.pop(val) # O(1)
                return True
            else:
                return False
    
        def getRandom(self):
            """
            Get a random element from the set.
            :rtype: int
            """
            return self.vals[randint(0, len(self.vals)-1)] # O(1)
    

    """


Log in to reply
 

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