Since we don't have multisets in Java, tried my luck to build one.
Reviews and feedbacks are welcome.
Basic idea is we keep another frequency map for each object. Whenever, we add an element, we update this frequency map as well. Whenever we remove, we check if that element now has frequency 0, if yes then only we remove it from set. Also we are using TreeSet so all the elements will be sorted and all TreeSet features are available out of the box.
I solved https://mirror.codeforces.com/contest/527/problem/C using this.
Submission — https://mirror.codeforces.com/contest/527/submission/116237858
static class MultiSet<T> extends TreeSet<T> {
Map<T, Integer> frequency;
public MultiSet() {
this.frequency = new HashMap<>();
}
@Override
public boolean add(T t) {
frequency.put(t, frequency.getOrDefault(t, 0) + 1);
return super.add(t);
}
@Override
public boolean remove(Object o) {
if (!frequency.containsKey(o))
return false;
frequency.put((T) o, frequency.getOrDefault(o, 1) - 1);
if (frequency.get(o) == 0) {
frequency.remove(o);
super.remove(o);
}
return true;
}
@Override
public String toString() {
return new StringJoiner(", ", MultiSet.class.getSimpleName() + "[", "]")
.add("frequency=" + frequency)
.add(super.toString())
.toString();
}
}
