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
Link:
https://leetcode.com/problems/lfu-cache/#/description
解题方法：
想要在O(1)的时候内完成get()由key映射到node的哈希表keyToNode是不可免的。
当内存满时，需要删除使用频率最少的数，如果有几个相同的数则删除最早的那个。所以可以想到要把相同频率的数归纳到一起，我们还需要另一个由频率映射到list的另一个哈希表freToList。每个list里面储存的是相同频率的不同node或key。
当使用get()函数时，我们需要专门找到某个node，使其频率+1。为了能在O(1)的时候内完成这个操作。每个node除了储存value，频率以外，还需要储存的是其在freToList里某个list的迭代器。
由此，在O(1)时间完成频率的更新和加减node都可以实现了。最后一步问题很容易让人想不明白：当需要删除最少使用的node时，如何得到最少频率minFre从而在freTolist进行操作？
有几个需要认清的细节可以解决这个问题：
1、当有新的node加入的时候，minFre一定为1。
2、使minFre不为1的情况只有进行get()成功的时候或者用put()更新一个node的value的时候。
3、以上两个操作都不会使一个数的频率进行跳跃增长（即每次都只会让一个数的频率+1）。
由以上3点可以得出我们怎样不会使minFre出错的方法：
1、当有新的数加入的时候，使minFre = 1；
2、当对一个数的频率进行更改后，如果freToList[minFre].size() == 0,那么minFre一定为minFre++。
Tips:
使用list来储存相同频率的数，每次从list的前面插入，要删除时从list的后面删除。这样每次就会删除最早的最少使用次数的node。
如果每次从后面插入那么迭代器不好赋值，原因如下：
Time Complexity：
O(1)
完整代码：
class Node
{
public:
int val;
int fre;
list<int>::iterator iter;
Node(int v, int f): val(v), fre(f) {}
};
class LFUCache
{
private:
unordered_map<int, Node*> keyToNode;
unordered_map<int, list<int>> freToList;
int capacity;
int size;
int minFre;
public:
LFUCache(int capacity)
{
size = 0;
this->capacity = capacity;
}
int get(int key)
{
if(keyToNode[key] == NULL)
return -1;
list<int>::iterator change = keyToNode[key]->iter;
freToList[keyToNode[key]->fre++].erase(change);
freToList[keyToNode[key]->fre].push_front(key);
keyToNode[key]->iter = freToList[keyToNode[key]->fre].begin();
if(freToList[minFre].size() == 0)
minFre++;
return keyToNode[key]->val;
}
void put(int key, int value)
{
if(capacity <= 0)
return;
if(keyToNode[key] == NULL)
{
Node* curr = new Node(value, 1);
freToList[1].push_front(key);
curr->iter = freToList[1].begin();
keyToNode[key] = curr;
size++;
if(size > capacity)
{
keyToNode.erase(freToList[minFre].back());
freToList[minFre].pop_back();
size--;
}
minFre = 1;
}
else
{
get(key);
keyToNode[key]->val = value;
}
}
};
