Like RandomizedSet but allows duplicates. All three operations must be O(1) on average.
insert(1)→true, insert(1)→false, insert(2)→true, getRandom()→1or2, remove(1)→true, getRandom()→1or2
Use a Map> and a List. On remove, swap with last element, update set of indices for both elements.
- Map> map; List list.
- insert: add to list, add index to map[val].
- remove: pick any index i for val; swap with last element; update indices; remove.
import java.util.*;
class RandomizedCollection {
Map<Integer, LinkedHashSet<Integer>> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
Random rand = new Random();
public boolean insert(int val) {
boolean absent = !map.containsKey(val) || map.get(val).isEmpty();
map.computeIfAbsent(val, k->new LinkedHashSet<>()).add(list.size());
list.add(val); return absent;
}
public boolean remove(int val) {
if (!map.containsKey(val) || map.get(val).isEmpty()) return false;
int idx = map.get(val).iterator().next();
int last = list.get(list.size()-1);
map.get(val).remove(idx);
if (idx < list.size()-1) {
list.set(idx, last);
map.get(last).remove(list.size()-1);
map.get(last).add(idx);
}
list.remove(list.size()-1); return true;
}
public int getRandom() { return list.get(rand.nextInt(list.size())); }
}
- Time Complexity: All O(1) average
- Space Complexity: O(N)