460 LFU

Design and implement a data structure forLeast Frequently Used (LFU)cache. It should support the following operations:getandput.

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 leastrecentlyused key would be evicted.

Follow up: Could you do both operations inO(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

我的实现绝对不是O(1)，O(1)的看了一下discuss，好象是用2个hashmap，一个<key, value>一个<key, node>，然后每个node是个doublelinkedlist，还用了linkedhashset。各种复杂，不明觉厉。过了一段时间做过432那题然后google了一番，终于发现那个数据结构就是实现LFU的数据结构。基本上就是hashmap保存key和node，每个node都存了access次数和对应的hashSet（linkedHashset，因为删除用得最小的值时，old的value会首先被删，这就刚好是linkedhashset的特性，用iterator，先进去的先出来）如果某一个值被access多一次的话，就remove from set，然后插到下一个节点which has + 1 frequency。

public class LFUCache {

    class Node {
        int key;
        int val;
        int freq;
        long ts;

        public Node(int k, int v, int f, long t) {
            key = k;
            val = v;
            freq = f;
            ts = t;
        }
    }

    int cap;
    //<key, node>
    HashMap<Integer, Node> hm;
    PriorityQueue<Node> freqQ;
    long systime;

    public LFUCache(int capacity) {
        cap = capacity;
        hm = new HashMap<>();
        systime = 0L;
        freqQ = new PriorityQueue(new Comparator<Node>() {
            public int compare(Node n1, Node n2) {
                if (n1.freq == n2.freq) {
                    return (int)(n1.ts - n2.ts);
                }
                return n1.freq - n2.freq;
            }
        });
    }

    public int get(int key) {
        if (cap < 1) { // don't need this ?
            return -1;
        }
        if (!hm.containsKey(key)) {
            return -1;
        }

        // if exist update freq & ts
        Node cur = hm.get(key);

        // need to remove & inseart again to update priorityQueue, or reordering won't kick in
        freqQ.remove((Object)cur);    

        cur.freq = cur.freq + 1; // cur.freq++;
        cur.ts = systime++;

        freqQ.offer(cur);

        return cur.val;
    }

    public void put(int key, int value) {
        if (cap < 1) {
            return;
        }
        if (get(key) != -1) {
            Node cur = hm.get(key); // combine into one
            cur.val = value;        //  hm.get(key).val = value;
            return;
        }

        // if it's full, remove least frequnt one
        if (freqQ.size() == cap) {
            Node old = freqQ.poll();
            hm.remove(old.key);
        }

        // need to create new node and inseart
        Node newNode = new Node(key, value, 1, systime++);
        hm.put(key, newNode);
        freqQ.offer(newNode);
    }
}

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