Python AC solution


  • 0

    EDITED:

    Thanks to @stachenov

    Use an array to store all element.
    Use a dictionary to store the appearane of each element. (key = val, value = set of index)

    To insert, simply add new element to the array and update the dictionary.
    To remove, first check the existance of this element with dictionary. (and get an arbitrary index)
    Swap it with the last element, and update the dictionary.
    To getRandom, directly use random.randint to get the index from the array.

    import random
    
    class RandomizedCollection(object):
        def __init__(self):
            self.collection = {}        # key = item stored in array, value = set of index
            self.array = []             # store all items in the array
    
        def insert(self, val):
            index = len(self.array)
            self.array += val,
    
            if val not in self.collection.keys():
                self.collection[val] = set([index])
                return True
            else:
                self.collection[val].add(index)
                return False
    
        def remove(self, val):
            if not self.array or val not in self.collection.keys():
                return False
    
            else:
                last = self.array[-1]                           # the other element
                i_last = len(self.array)-1                      # index of last position
                i_val = self.collection[val].pop()              # index of val position
                self.array[i_val] = self.array[i_last]          # update the array
                self.array.pop()
    
                self.collection[last].add(i_val)                # update the dict
                self.collection[last].remove(i_last)
    
                if len(self.collection[val]) == 0:
                    del self.collection[val]                    # remove empty set
                
                return True
    
        def getRandom(self):
            if len(self.array) == 0: return -1
            else: return self.array[random.randint(0, len(self.array)-1)]
    

    Original Post:

    Similar to #380, which can be solved just using set().

    In order to deal with duplication here, use one more dictionary to store the appearance of each element. (key = val, value = appearance). In the sets, we can store each val as a tuple: (val, appearance)

    For example, if input = [insert 1, insert 2, insert 1], then the set will be: set((1,1), (2,1), (1,2))

    For deleting, just see whether val is in dictionary or not. If exist, remove the one with the latest appearance in the set. (And also fix the dictionary)

    For sampling, just sample as #380, but only return the val part.

    It should be one of the easiest way.

    import random
    
    class RandomizedCollection(object):
        def __init__(self):
            self.collection = {}        # key = val, value = appearances
            self.data = set()           # store val with appearance
    
        def insert(self, val):
            if val not in self.collection.keys():
                self.collection[val] = 1
                self.data.add((val, 1))
                return True
            else:
                self.collection[val] += 1
                self.data.add((val, self.collection[val]))
                return False
    
        def remove(self, val):
            # if exist => remove it from dictionary and set
            # if appearances == 0 => remove from the dictionary
    
            if val in self.collection.keys():
                self.data.remove((val, self.collection[val]))
                self.collection[val] -= 1
                if self.collection[val] == 0: del self.collection[val]
                return True
            else:
                return False
    
        def getRandom(self):
            return random.sample(self.data, 1)[0][0]
    

  • 1

    Are you sure that random.sample is O(1)? Because I can't imagine how it could work. Looking at its sources, it seems more like O(n) to me because as far as I can understand, it converts the set to a list.


  • 0

    @stachenov Thanks for your correction! You're right. It also can be found at L309 of random.py. I'm gonna fix my code.


Log in to reply
 

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