2 Python implementations using dictionary and list (Syned and Asyned), with explanation


  • 5
    O

    Quite a number of people have posted their C++ code based on the same idea, which is:

    1. A plain list does most of the job. It makes sure insert and getRandom is O(1).
    2. The dictionary comes in handy when you need to make remove O(1). The dictionary maps the values to their indices in the list, so when you want to quickly remove something from the list, you always know where to start.

    So, here come 2 flavors:

    Synced version, in which the list and dictionary are always having the same size.
    No actual swapping is needed for remove because the last element of the list is always going to be popped out, anyway. Don't bother to write to the last slot.

    import random
    class RandomizedSet(object):
        def __init__(self):
            self.l = []
            self.d = {}
    
        def insert(self, val):
            if val in self.d:
                return False
            self.d[val] = len(self.l)
            self.l.append(val)
            return True        
    
        def remove(self, val):
            if val not in self.d:
                return False
            i, newVal = self.d[val], self.l[-1]
            self.l[i], self.d[newVal] = newVal, i
            del self.d[val]
            self.l.pop()
            return True
    
        def getRandom(self):
            return random.choice(self.l)
    

    Asynced version, in which I use the dict to keep track of the array size so I can avoid shrinking the list.

    import random
    class RandomizedSet(object):
    
        def __init__(self):
            self.l = []
            self.d = {}
    
        def insert(self, val):
            if val in self.d:
                return False
            i = len(self.d)
            self.d[val] = i
            if i < len(self.l):
                self.l[i] = val
            else:
                self.l.append(val)
            return True        
    
        def remove(self, val):
            if val not in self.d:
                return False
            i, newVal = self.d[val], self.l[len(self.d)-1]
            self.l[i], self.d[newVal] = newVal, i
            del self.d[val]
            return True
    
        def getRandom(self):
            return self.l[random.randrange(len(self.d))]
    

    The first implementation is shorter and cleaner, but i may prefer the second one in real life because it has less memory expansion and shrinking.


  • 0

    The dictionary is essential for insert as well, for the val in self.d check.

    Nice idea, your non-shrinking-list version. But why do you do the full swap there?


  • 0
    O

    @StefanPochmann No good reason. It was an old iteration. I have corrected it!


  • 0
    G

    Great idea, thanks!


  • 0
    G

    @o_sharp said in 2 Python implementations using dictionary and list (Syned and Asyned), with explanation:

        if val in self.d:
            return False
        self.d[val] = len(self.l)
        self.l.append(val)
        return True 
    

    Why does the time shoot way up if I do:
    "if val in self.l" instead of "if val in self.d",
    Basically, why is checking if something is in a dictionary way faster than if something is in a list for python?


Log in to reply
 

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