460. LFU Cache

题目解析

题目要求实现一个LFU Cache，提供put、get两个操作。LFU就是 Least Frequently Used，也就是对每个key都会对它的操作进行计数count，但容器满了以后，把count最小的那个数删掉（如果最小的count有两个元素，那么按LRU来选择，即最早添加的删除）。
之所以它是hard，主要是因为它要求get和put的操作为O(1)。在LRU那道题里面使用一个list来保存所有的元素，使用unordered_map来保存key对应的list节点。现在需要保存key对应的count，以及根据count快速找到list节点。

方法

使用一个unordered_map<int, list<pair<int, int>>> count_to_keys来保存count对应的元素，int low_count保存当前最小count。这个最小的count主要用于删除节点使用。
关键函数是update(), 它会更新key对应的节点，具体逻辑看代码即可。

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
        size = 0;
    }
    
    int get(int key) {
        if (size == 0 || key_to_value.find(key) == key_to_value.end()) {
            return -1;
        }
     
        int value = key_to_value[key]->second;
        update(key, value);
        return value;
    }
    
    void put(int key, int value) {
        if (cap == 0) return;
        if (key_to_value.find(key) != key_to_value.end()) {
            update(key, value);
            return;
        }
        if (size == cap) delete_last();
        insert_first(key, value);
    }
private:
    void update(int key, int value) {
        /*
        这个函数用于更新 (key, value)的count，
        比如get中，每使用一次get会增加key的count，
        比如put针对已有的key时，也会增加它的count，同时更新value
        */
        auto iter = key_to_value[key];
        int count = key_to_count[key];
        int new_count = count + 1;
        count_to_keys[count].erase(iter);
        
        if (low_count == count && count_to_keys[count].size() == 0) {  // 末尾最后一个元素更新
            low_count = new_count;
        }
        
        count_to_keys[new_count].push_front(make_pair(key, value));  // 插入到count对应的头部（LRU）
        auto new_iter = count_to_keys[new_count].begin();
        key_to_value[key] = new_iter;
        key_to_count[key] = new_count;
    }
    
    void delete_last() {
        /*
        删除count最小的最早的元素
        */
        auto iter = count_to_keys[low_count].end(); // LRU指定删除最早的节点
        iter--;
        int key = iter->first;
        key_to_value.erase(key);
        key_to_count.erase(key);
        count_to_keys[low_count].erase(iter);
        size--;
    }
    
    void insert_first(int key, int value) {
        /*
        添加count=0的元素
        */        
        size++;
        count_to_keys[0].push_front(make_pair(key, value));
        auto iter = count_to_keys[0].begin();
        key_to_value[key] = iter;
        key_to_count[key] = 0;
        if (low_count != 0) low_count = 0;
    }
    unordered_map<int, list<pair<int, int>>::iterator> key_to_value;
    unordered_map<int, list<pair<int, int>>> count_to_keys;
    unordered_map<int, int> key_to_count;
    
    int cap;
    int low_count = 0;
    int size;
};