460. LFU Cache

Problem:

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.

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

8/13/2018 update:
put是分两种情况
1. 当前元素在cache里面
2. 当前元素不在cache里面，如果超过则evict, 然后插入进freq 1里面
--------------------------------------------------------------------------------------------------------------------------
Analysis:
用3个数据结构来辅助
Map<Integer, Integer> values store : vals
Map<Integer, Integer> key 和频率 : counts
Map<Iinteger, LinkedHashSet<Integer>> 频率和当前频率对应的key :freqs
同时记录min frequency。

如果超过了capacity，则freqs.get(min)中选取第一个删除。如果是新加的value,则更新min为1.

走一遍题目中的例子
1. put(1, 1) put(2, 2)
    vals: {1,1}, {2,2}
    counts: {1,1}, {2,1}
    freqs: {1, {1,2}}
    min = 1
2. get(1) 返回1
     counts: {1, 2}, {2, 1}
     freqs: {1, {2}}, {2, {1}}
     1 使用过一次freqency加1
    min  = 1
3. put(3, 3)
     超过了capacity,删除freqs.get(1)中的第一个也就是2

Solution:
在put的时候可以复用get进行频率的修改


   

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

class LFUCache { Map<Integer, Integer> counts; Map<Integer, Integer> vals; Map<Integer, LinkedHashSet<Integer>> freqs; int min; int capacity; public LFUCache(int capacity) { counts = new HashMap<>(); vals = new HashMap<>(); freqs = new HashMap<>(); min = Integer.MAX_VALUE; this.capacity = capacity; freqs.put(1, new LinkedHashSet<>()); } public int get(int key) { if (!vals.containsKey(key)) return -1; int count = counts.get(key); freqs.get(count).remove(key); freqs.computeIfAbsent(count + 1, k -> new LinkedHashSet<>()).add(key); counts.put(key, count + 1); if (count == min && freqs.get(count).size() == 0) min = count + 1; return vals.get(key); } public void put(int key, int value) { if (capacity <= 0) return; // update counts, vals, and freqs if (get(key) != -1) { vals.put(key, value); return; } if (vals.size() >= capacity) { int keyToRemove = freqs.get(min).iterator().next(); counts.remove(keyToRemove); vals.remove(keyToRemove); freqs.get(min).remove(keyToRemove); } vals.put(key, value); counts.put(key, 1); min = 1; freqs.get(1).add(key); } } /** * 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); */