-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_460.java
More file actions
64 lines (58 loc) · 2 KB
/
Copy pathP_460.java
File metadata and controls
64 lines (58 loc) · 2 KB
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
53
54
55
56
57
58
59
60
61
62
63
64
package leetcode.hard;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
@SuppressWarnings("unused")
public class P_460 {
static class LFUCache {
Map<Integer, Integer> cache = new HashMap<>();
Map<Integer, Integer> freq1 = new HashMap<>();
Map<Integer, Set<Integer>> freq2 = new HashMap<>();
int cap;
int min;
LFUCache(int capacity) {
cap = capacity;
}
public int get(int key) {
if (cache.containsKey(key)) {
final int oldFreq = freq1.merge(key, 1, Integer::sum) - 1;
if (oldFreq > 0) {
freq2.get(oldFreq).remove(key);
if (freq2.get(oldFreq).isEmpty()) {
freq2.remove(oldFreq);
if (min == oldFreq) {
min = oldFreq + 1;
}
}
}
freq2.computeIfAbsent(oldFreq + 1, val -> new LinkedHashSet<>()).add(key);
}
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
if (cap == 0) {
return;
}
if (cache.containsKey(key)) {
get(key);
} else {
if (cache.size() == cap) {
final Iterator<Integer> iterator = freq2.get(min).iterator();
final int removeKey = iterator.next();
iterator.remove();
cache.remove(removeKey);
freq1.remove(removeKey);
if (freq2.get(min).isEmpty()) {
freq2.remove(min);
}
}
freq1.merge(key, 1, Integer::sum);
freq2.computeIfAbsent(1, val -> new LinkedHashSet<>()).add(key);
min = 1;
}
cache.put(key, value);
}
}
}