Python Nested dict solution


  • 0
    A
    from random import randint
    from collections import defaultdict
    class RandomizedCollection(object):
        
        def __init__(self):
           
            self.od = defaultdict(dict)
            self.L = [] 
    
        def insert(self, val):
           
            self.od[val][len(self.L)] = True
            self.L.append(val)
            return True
            
        def remove(self, val):
           
           
            if val in self.od:
                # swap any instance with last element and delete last
                i, newVal = self.od[val].keys()[0], self.L[-1]
                
                # delete len(self.L) - 1 from newVal
                del self.od[newVal][len(self.L) - 1]
                self.L[i] = newVal
                self.od[newVal][i] = True
                
                # reduce collection size
                del self.L[-1]
                
                # remove one entry form dict list and remove val if empty list
                del self.od[val][i]
                if len(self.od[val]) == 0:
                    del self.od[val]
                    
                return True
            return False
    
        def getRandom(self):
           
            if len(self.L) == 0: return -1
            if len(self.L) == 1: return self.L[0]
            r = randint(0, len(self.L) - 1)
            return self.L[r]
            
    
    
    # Your RandomizedCollection object will be instantiated and called as such:
    # obj = RandomizedCollection()
    # param_1 = obj.insert(val)
    # param_2 = obj.remove(val)
    # param_3 = obj.getRandom()
    

  • 0

    This is not O(1). You can't call .keys() since it's O(n).


Log in to reply
 

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