# 460 - LFU Cache

這題是擴展眼界題，邊聽影片邊做，可以看：https://www.youtube.com/watch?v=MCTN3MM8vHA

解法一 - Hash Table + balanced binary search tree (C++ 裡的 set)

這個解法雖然 get 和 put 的時間複雜度都是 O(logC)，C 是 capacity，不過是一般人比較容易想到的，所以還是把程式碼敲一下感受感受：

struct CacheNode {
    int key;
    int value;
    int freq;
    long tick;

    bool operator < (const CacheNode& rhs) const {
        if(freq < rhs.freq) return true;
        if(freq == rhs.freq) return tick < rhs.tick;
        return false;
    }
};

class LFUCache {
public:
    LFUCache(int capacity) {
        capacity_ = capacity;
        tick_ = 0;
    }

    int get(int key) {
        auto it = m_.find(key);
        if(it == m_.end()) { return -1; }
        touch(it->second);
        return it->second.value;
    }

    void put(int key, int value) {
        if(capacity_ == 0) {
            return;
        }

        auto it = m_.find(key);

        if(it != m_.end()) {
            it->second.value = value;
            touch(it->second);
            return;
        }

        if(m_.size() == capacity_) {
            CacheNode node = *cache_.begin();
            m_.erase(node.key);
            cache_.erase(node);
        }

        CacheNode node{key, value, 1, ++tick_};
        m_[key] = node;
        cache_.insert(node);
    }

private:
    void touch(CacheNode& node) {
        cache_.erase(node);
        ++node.freq;
        node.tick = ++tick_;
        cache_.insert(node);
    }    

    long tick_;
    int capacity_;
    unordered_map<int, CacheNode> m_;
    set<CacheNode> cache_;
};

/**
 * 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);
 */