Sponsored
Sponsored
This approach uses a HashMap to store the indices of elements and a List to store the elements themselves. The HashMap enables quick updates for insertions and deletions, while the List ensures that we can select a random element efficiently.
We maintain a Count of all elements using a map, where each element maps to a set of indices in the List. During removal, we swap the element with the last element in the list (if not already last), update the HashMap accordingly, and remove the last entry from the list for O(1) complexity.
Time Complexity: O(1) average for all operations.
Space Complexity: O(n), where n is the number of elements in the multiset.
1import random
2
3class RandomizedCollection:
4
5 def __init__(self):
6 self.lst = []
7 self.indices = {}
8
9 def insert(self, val: int) -> bool:
10 isNew = val not in self.indices
11 if val not in self.indices:
12 self.indices[val] = set()
13 self.indices[val].add(len(self.lst))
14 self.lst.append(val)
15 return isNew
16
17 def remove(self, val: int) -> bool:
18 if val not in self.indices or not self.indices[val]:
19 return False
20 remove_idx = self.indices[val].pop()
21 last_val = self.lst[-1]
22 self.lst[remove_idx] = last_val
23 if self.indices[last_val]:
24 self.indices[last_val].add(remove_idx)
25 self.indices[last_val].discard(len(self.lst) - 1)
26 self.lst.pop()
27 if not self.indices[val]:
28 del self.indices[val]
29 return True
30
31 def getRandom(self) -> int:
32 return random.choice(self.lst)
33The Python solution uses a dictionary to keep track of indices where each value is located in the list. Insertion simply adds the value to the list and its index to the dictionary. Deletion involves swapping the element to be removed with the last element if it is not the last, then removing it efficiently. Getting a random element uses Python's built-in random.choice method for lists.