/
AllOne.java
52 lines (43 loc) · 1.39 KB
/
AllOne.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// https://leetcode.com/problems/all-oone-data-structure
class AllOne {
TreeMap<Integer, TreeSet<String>> rev;
Map<String, Integer> freq;
public AllOne() {
freq = new HashMap<>();
rev = new TreeMap<>();
}
public void inc(String key) {
update(key, 1);
//System.out.println("Incremented " + key + ", rev = " + rev);
}
public void dec(String key) {
update(key, -1);
rev.remove(0);
//System.out.println("Decremented " + key + ", rev = " + rev);
}
private void update(String key, int inc) {
int curr = freq.getOrDefault(key, 0);
if (curr > 0) {
TreeSet<String> set = rev.get(curr);
set.remove(key);
rev.put(curr, set);
if (set.isEmpty()) {
rev.remove(curr);
}
}
TreeSet<String> newSet = rev.getOrDefault(curr + inc, new TreeSet<>());
newSet.add(key);
rev.put(curr + inc, newSet);
freq.put(key, curr + inc);
}
public String getMaxKey() {
//System.out.println("Max");
if (rev.isEmpty()) return "";
return rev.lastEntry().getValue().first();
}
public String getMinKey() {
//System.out.println("Min");
if (rev.isEmpty()) return "";
return rev.firstEntry().getValue().first();
}
}