Description
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LFUCache cache = new LFUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
Solution
Two HashMap + DoublyLinkedList, O(1), S(capacity)
真的是難題啊杈笔，邏輯算很復雜的了，非常容易出bug糕非。
思路基于LRU Cache蒙具，為了支持O(1) evict lease frequently used element，需要有一個freqMap<Integer, DLL>朽肥，還需要一個int minFreq禁筏，這樣就夠了。
一個比較tricky的地方是衡招，minFreq的更新好像很麻煩篱昔。但實際上沒有想象中的復雜，minFreq的更新是有跡可循的始腾。
- 當update node時州刽，要判斷node是否已經(jīng)存在：
- 如果node存在，node.freq++窘茁，如果node.oldFreq == minFreq怀伦，可能需要刪除minFreqList，這時只需判斷minFreqList在更新之后是否為空即可山林。
- 不為空：minFreq保持不變
- 為空：minFreq++即可，因為node.newFreq = node.oldFreq + 1邢羔，且它一定變成了新的minFreq
- 如果node不存在驼抹，那么需要新建node，node.freq = 1拜鹤。minFreq自然就變成1了框冀，因為1是可能出現(xiàn)的最小freq！
- 如果node存在，node.freq++窘茁，如果node.oldFreq == minFreq怀伦，可能需要刪除minFreqList，這時只需判斷minFreqList在更新之后是否為空即可山林。
- 當evict node時敏簿，感覺minFreq的更新會變得復雜是不是明也，因為可能需要找到secondMinFreq對嗎宣虾？但實際情況很簡單，因為evict node一定是跟initialize node成對兒出現(xiàn)的（只有在達到capacity時）温数，所以可以回歸到上面的update node node為空的情況绣硝，minFreq一定會變成1。刺不刺激撑刺？
注意以下幾個坑：
- Node或List的創(chuàng)建或銷毀鹉胖，一定要跟Map的更新同步操作！否則會出現(xiàn)不一致够傍。
- 注意處理capacity == 0的情況
class LFUCache {
class Node {
Node prev, next;
int key, val, freq;
public Node(int k, int v) {
key = k;
val = v;
freq = 1; // initial freq is always 1
}
}
class DLL {
Node head, tail;
int size;
public DLL() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
// add node after head
public void add(Node node) {
head.next.prev = node;
node.next = head.next;
node.prev = head;
head.next = node;
++size;
}
public void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
--size;
}
public Node removeLast() {
Node last = tail.prev;
remove(last);
return last;
}
public boolean isEmpty() {
return size == 0;
}
}
private int capacity;
private int minFreq;
private Map<Integer, Node> nodeMap;
private Map<Integer, DLL> freqMap;
public LFUCache(int capacity) {
this.capacity = capacity;
minFreq = 0; // initial minFreq is 0 of course
nodeMap = new HashMap<>();
freqMap = new HashMap<>();
}
public int get(int key) {
if (!nodeMap.containsKey(key)) {
return -1;
}
Node node = nodeMap.get(key);
update(node);
return node.val;
}
public void put(int key, int val) {
if (capacity < 1) { // if capacity is 0, we shouldn't make any change
return;
}
if (nodeMap.containsKey(key)) {
Node node = nodeMap.get(key);
node.val = val;
update(node);
} else {
if (nodeMap.size() == capacity) {
evict();
}
Node node = new Node(key, val);
nodeMap.put(key, node);
minFreq = 1; // update minFreq to 1! Because curr node is a new one
DLL newList = freqMap.getOrDefault(node.freq, new DLL());
freqMap.put(node.freq, newList);
newList.add(node);
}
}
// handle the tricky logic to move node from oldFreqList to newFreqList
// don't forget to update minFreq if old freq list is the minFreq and empty
private void update(Node node) {
// deal with old freq list
int oldFreq = node.freq;
DLL oldList = freqMap.get(oldFreq);
oldList.remove(node);
if (oldList.isEmpty()) { // evict empty freq list
freqMap.remove(oldFreq);
if (oldFreq == minFreq) { // if the removed freq list is the min
++minFreq; // just increase the minFreq because freqs are consequtive!
}
}
// deal with new freq list
++node.freq;
DLL newList = freqMap.getOrDefault(node.freq, new DLL());
freqMap.put(node.freq, newList);
newList.add(node);
}
// evict lease frequently used node
private void evict() {
Node last = freqMap.get(minFreq).removeLast();
nodeMap.remove(last.key);
}
}
/**
* 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);
*/
Three HashMap + LinkedHashSet, O(1), S(capacity)
在Java中可以利用LinkedHashSet來當做DoublyLinkedList甫菠。
A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. When the iteration order is needed to be maintained this class in used. When iterating through a HashSet the order is unpredictable, while a LinkedHashSet lets us iterate through the elements in the order in which they were inserted.when cycling through LinkedHashSet using an iterator, the elements will be returned in the order in which they were inserted.
LinkedHashSet內(nèi)部應該是一個HashMap + DoublyLinkedList，其特性為：
- 包含HashSet的一切特性：unique value冕屯，O(1) get, put
- remains insertion order：用iterator遍歷時會按照插入順序從老到新寂诱。
下面的代碼就是用LinkedHashSet作為DLL的實現(xiàn)，思路跟上面的方案是一致的安聘。
class LFUCache {
private int capacity;
private int minFreq;
private Map<Integer, Integer> valMap;
private Map<Integer, Integer> freqMap;
private Map<Integer, Set<Integer>> freqSetMap;
public LFUCache(int capacity) {
this.capacity = capacity;
minFreq = 0;
valMap = new HashMap<>();
freqMap = new HashMap<>();
freqSetMap = new HashMap<>();
}
public int get(int key) {
if (!valMap.containsKey(key)) {
return -1;
}
update(key);
return valMap.get(key);
}
public void put(int key, int val) {
if (capacity < 1) {
return;
}
if (valMap.containsKey(key)) {
valMap.put(key, val);
update(key);
} else {
if (valMap.size() == capacity) {
evict();
}
valMap.put(key, val);
freqMap.put(key, 1);
freqSetMap.put(1, freqSetMap.getOrDefault(1, new LinkedHashSet<>()));
freqSetMap.get(1).add(key);
minFreq = 1;
}
}
private void update(int key) {
int oldFreq = freqMap.get(key);
int newFreq = oldFreq + 1;
freqMap.put(key, newFreq);
Set<Integer> oldFreqSet = freqSetMap.get(oldFreq);
oldFreqSet.remove(key);
if (oldFreqSet.isEmpty()) {
freqSetMap.remove(oldFreq);
if (oldFreq == minFreq) {
++minFreq;
}
}
Set<Integer> newFreqSet = freqSetMap.getOrDefault(newFreq, new LinkedHashSet<>());
freqSetMap.put(newFreq, newFreqSet);
newFreqSet.add(key);
}
private void evict() {
Set<Integer> minFreqSet = freqSetMap.get(minFreq);
int lastKey = minFreqSet.iterator().next();
minFreqSet.remove(lastKey);
valMap.remove(lastKey);
freqMap.remove(lastKey);
if (minFreqSet.isEmpty()) {
freqSetMap.remove(minFreq); // minFreq should be set to 1 later
}
}
}
/**
* 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);
*/
