460.LFU Cache
===

###### tags: `Hard`,`Hash Table`,`Design`,`Linked List`

[460. LFU Cache](https://leetcode.com/problems/lfu-cache/)

### 題目描述
Design and implement a data structure for a [Least Frequently Used (LFU)](https://en.wikipedia.org/wiki/Least_frequently_used) cache.

Implement the `LFUCache` class:

* `LFUCache(int capacity)` Initializes the object with the `capacity` of the data structure.
* `int get(int key)` Gets the value of the `key` if the `key` exists in the cache. Otherwise, returns `-1`.
* `void put(int key, int value)` Update the value of the `key` if present, or inserts the `key` if not already present. When the cache reaches its `capacity`, 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 used** `key` 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=[4,3], cnt(4)=2, cnt(3)=3

**Constraints**:

* 0 <= `capacity` <= 10^4^
* 0 <= `key` <= 10^5^
* 0 <= `value` <= 10^9^
* At most 2 * 10^5^ calls will be made to `get` and `put`.

### 解答
#### C++

struct Node {
    int key;
    int value;
    int freq;
    list<int>::const_iterator pos;
};

class LFUCache {
    int capacity;
    int min_freq;
    unordered_map<int, list<int>> freq_list;
    unordered_map<int, Node> cache;
public:
    LFUCache(int capacity): capacity(capacity) {
        
    }
    
    void update(Node& node) {
        freq_list[node.freq].erase(node.pos);
        if (freq_list[node.freq].empty()) {
            freq_list.erase(node.freq);
            if (node.freq == min_freq) min_freq++;
        }
        node.freq++;
        freq_list[node.freq].push_front(node.key);
        node.pos = freq_list[node.freq].cbegin();
    }

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        Node& node = it->second;
        update(node);
        return node.value;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return;
        auto it = cache.find(key);
        if (it != cache.end()) {
            Node& node = it->second;
            node.value = value;
            update(node);
            return;
        }
        if (cache.size() == capacity) {
            cache.erase(freq_list[min_freq].back());
            freq_list[min_freq].pop_back();
        }
        min_freq = 1;
        freq_list[1].push_front(key);
        cache[key] = {key, value, 1, freq_list[1].cbegin()};
    }
};

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)