> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/jian-guo/460.-lfu-cache.md).

# 460. LFU Cache

实现LFU，即cache满了后找使用频率最低的移除，如果有多个同最低频率的则移除最后没使用过的。找频率最低的可以用heap或tree set根据freq存数据，但这么做每次操作需要O(lgN)时间。如果不考虑频率，题目就退成了LRU cache，用double linked list配合hash map。现在引入频率，相当于对每个频率都维持了一个LRU cache，当然为了方便查找它们共用一个hash map。

![](https://pic4.zhimg.com/80/v2-1ff3ee7d53cf657916d1b822a3ebcc57_hd.jpg)

答案参考了[花花](https://link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3DMCTN3MM8vHA)的。

```cpp
/*
 * @lc app=leetcode id=460 lang=cpp
 *
 * [460] LFU Cache
 *
 * https://leetcode.com/problems/lfu-cache/description/
 *
 * algorithms
 * Hard (29.73%)
 * Likes:    842
 * Dislikes: 90
 * Total Accepted:    49.1K
 * Total Submissions: 161.3K
 * Testcase Example:  '["LFUCache","put","put","get","put","get","get","put","get","get","get"]\n[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]'
 *
 * 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.
 * 
 * Note that the number of times an item is used is the number of calls to the
 * get and put functions for that item since it was inserted. This number is
 * set to zero when the item is removed.
 * 
 * 
 * 
 * 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
 * 
 * 
 * 
 * 
 */

// @lc code=start
class LFUCache {
public:
    class Node {
    public:
        int key;
        int val;
        int freq;
        list<int>::const_iterator it;
        Node(int k, int v, int f, list<int>::const_iterator i): key(k), val(v), freq(f), it(i) {}
    };

    int cap, min_freq;
    unordered_map<int, Node*> m;
    unordered_map<int, list<int>> freqs;

    LFUCache(int capacity) {
        cap = capacity;
        min_freq = 0;
    }

    void touch(Node *node) {
        // update the freq
        const int prev_freq = node->freq;
        const int freq = ++(node->freq);
        // rm the node from old freq list
        freqs[prev_freq].erase(node->it);
        if (freqs[prev_freq].empty() && prev_freq == min_freq) {
            freqs.erase(prev_freq);
            ++min_freq;
        }
        // insert the key to the front of the new freq list
        freqs[freq].push_front(node->key);

        // update the pointer
        node->it = freqs[freq].cbegin();
    }
    
    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        touch(it->second);
        return it->second->val;
    }
    
    void put(int key, int value) {
        if (cap == 0) return;
        auto it = m.find(key);
        if (it != m.cend()) {
            it->second->val = value;
            touch(it->second); 
            return;
        }
        if (m.size() == cap) {
            // full, need to remove
            // rm from the min_freq list
            const int key_to_del = freqs[min_freq].back();
            freqs[min_freq].pop_back();
            m.erase(key_to_del);
        }
        min_freq = 1;
        freqs[min_freq].push_front(key);
        m[key] = new Node(key, value, min_freq, freqs[min_freq].cbegin());
    }
};

/**
 * 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);
 */
// @lc code=end


```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/hash/jian-guo/460.-lfu-cache.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.