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 java.util.*;
2
3public class RandomizedCollection {
4 private List<Integer> nums;
5 private Map<Integer, Set<Integer>> indices;
6 private Random rand;
7
8 public RandomizedCollection() {
9 nums = new ArrayList<>();
10 indices = new HashMap<>();
11 rand = new Random();
12 }
13
14 public boolean insert(int val) {
15 boolean contained = indices.containsKey(val);
16 if (!contained) indices.put(val, new LinkedHashSet<>());
17 indices.get(val).add(nums.size());
18 nums.add(val);
19 return !contained;
20 }
21
22 public boolean remove(int val) {
23 if (!indices.containsKey(val) || indices.get(val).isEmpty()) return false;
24 int removeIndex = indices.get(val).iterator().next();
25 indices.get(val).remove(removeIndex);
26 int last = nums.get(nums.size() - 1);
27 nums.set(removeIndex, last);
28 if (indices.get(last).contains(nums.size() - 1)) {
29 indices.get(last).remove(nums.size() - 1);
30 indices.get(last).add(removeIndex);
31 }
32 nums.remove(nums.size() - 1);
33 if (indices.get(val).isEmpty()) indices.remove(val);
34 return true;
35 }
36
37 public int getRandom() {
38 return nums.get(rand.nextInt(nums.size()));
39 }
40}The Java solution uses an ArrayList to store the numbers and a HashMap from integer values to index sets of their positions in the list. Insertions add the value to the list and map the index in the set. Deletion swaps with the last element and deletes, while getRandom retrieves an element using the Random class for arrays.