0460. LFU Cache
https://leetcode.com/problems/lfu-cache
Description
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache
class:
LFUCache(int capacity)
Initializes the object with thecapacity
of the data structure.int get(int key)
Gets the value of thekey
if thekey
exists in the cache. Otherwise, returns-1
.void put(int key, int value)
Update the value of thekey
if present, or inserts thekey
if not already present. When the cache reaches itscapacity
, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently usedkey
would be invalidated.
To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1
(due to the put
operation). The use counter for a key in the cache is incremented either a get
or put
operation is called on it.
The functions get
and put
must each run in O(1)
average time complexity.
Example 1:
**Input**
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
**Output**
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
**Explanation**
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,\_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
Constraints:
0 <= capacity <= 104
0 <= key <= 105
0 <= value <= 109
At most
2 * 105
calls will be made toget
andput
.
ac
class LFUCache {
int min, capacity;
Map<Integer, Integer> keyToValue, keyToFreq;
Map<Integer, LinkedHashSet<Integer>> freqBucket;
public LFUCache(int capacity) {
this.capacity = capacity;
min = 0;
keyToValue = new HashMap<>();
keyToFreq = new HashMap<>();
freqBucket = new HashMap<>();
}
public int get(int key) {
if (!keyToValue.containsKey(key)) return -1;
addFreq(key);
return keyToValue.get(key);
}
public void put(int key, int value) {
if (capacity <= 0) return;
if (keyToValue.containsKey(key)) { // update old value
keyToValue.put(key, value);
addFreq(key);
} else { // add new value
if (keyToValue.size() == capacity) removeLeastFreq();
keyToValue.put(key, value);
addFreq(key);
}
}
private void addFreq(int key) {
int freq = keyToFreq.getOrDefault(key, 0);
keyToFreq.put(key, freq+1); // update freq
if (freq == 0) min = 1; // you just add a new element, min must be 1
if (freq > 0) removeKeyInFreqList(freq, key);
if (!freqBucket.containsKey(freq+1)) freqBucket.put(freq+1, new LinkedHashSet<>());
freqBucket.get(freq+1).add(key);
}
private void removeLeastFreq() {
while (freqBucket.get(min).size() == 0) min++;
int minKey = freqBucket.get(min).iterator().next();
removeKeyInFreqList(min, minKey);
keyToValue.remove(minKey);
keyToFreq.remove(minKey);
}
private void removeKeyInFreqList(int freq, int key) {
freqBucket.get(freq).remove(key);
if(min == freq && freqBucket.get(freq).size() == 0) min++;
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
/*
priority queue + hashmap, O(logn)
key:value
key:freq
key:freq-key
*/
Last updated
Was this helpful?