460、LFU缓存
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
题解
- 解决get的时间复杂度为$O(1)$——Map
- 解决put的时间复杂度为$O(1)$——有序集合，按照频率排序
HashMap + TreeSet
class LFUCache {
// 节点类，具有大小比较的能力
class Node implements Comparable<Node> {
// 频率
int cnt;
// 上一次访问的时间
int time;
// key value
int key;
int value;
public Node(int cnt,int time,int key,int value) {
this.cnt = cnt;
this.time = time;
this.key = key;
this.value = value;
}
// 频率比较器
@Override
public int compareTo(Node n1) {
return this.cnt == n1.cnt ? this.time - n1.time : this.cnt - n1.cnt;
}
}
int capacity,time;
Map<Integer,Node> keyTable;
TreeSet<Node> set;
public LFUCache(int capacity) {
this.capacity = capacity;
keyTable = new HashMap<>(capacity);
time = 0;
set = new TreeSet<Node>();
}
public int get(int key) {
// 0 容量
if (capacity == 0) {return -1;}
// key不存在
if (!keyTable.containsKey(key)) {
return -1;
}
// 更新节点状态
Node cache = keyTable.get(key);
set.remove(cache);
cache.cnt += 1;
cache.time = ++time;
set.add(cache);
keyTable.put(key,cache);
// 返回目标的值
return cache.value;
}
public void put(int key, int value) {
// 0 容量
if (capacity == 0) {return;}
// 数据不存在
if (!keyTable.containsKey(key)) {
// 达到容量了，删除最久未访问的
if (keyTable.size() == capacity) {
Node node = set.first();
System.out.println("node: "+node.key);
keyTable.remove(node.key);
set.remove(node);
}
// 插入新的值
Node node = new Node(1,++time,key,value);
keyTable.put(key,node);
set.add(node);
}else {
// 更新节点状态
Node cache = keyTable.get(key);
set.remove(cache);
cache.cnt += 1;
cache.time = ++time;
cache.value = value;
keyTable.put(key,cache);
set.add(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);
*/
双HashMap
- key-node map
- ferq-nodelist map
class LFUCache {
class Node {
int key,val;
int freq;
public Node(int key,int val,int freq) {
this.key = key;
this.val = val;
this.freq = freq;
}
}
int minfreq,capacity;
Map<Integer,Node> keyTable;
Map<Integer,LinkedList<Node>> freqTable;
private void update(int key,int val,int freq) {
Node newNode = new Node(key,val,freq);
LinkedList<Node> nodeList = freqTable.get(freq) == null ? new LinkedList<>():freqTable.get(freq);
nodeList.addFirst(newNode);
freqTable.put(freq,nodeList);
keyTable.put(key,newNode);
}
public LFUCache(int capacity) {
minfreq = 0;
this.capacity = capacity;
keyTable = new HashMap<>();
freqTable = new HashMap<>();
}
public int get(int key) {
// 0 容量
if (capacity == 0) {return -1;}
// key不存在
if(!keyTable.containsKey(key)) {
return -1;
}
// 移除以便更新节点的频率
Node node = keyTable.get(key);
int val = node.val, freq = node.freq;
freqTable.get(freq).remove(node);
// 列表为空了
if (freqTable.get(freq).isEmpty()) {
// 移除
freqTable.remove(freq);
if (minfreq == freq) {minfreq += 1;}
}
update(key,val,freq+1);
return node.val;
}
public void put(int key, int value) {
if (capacity == 0) {return;}
if (!keyTable.containsKey(key)){
// 满了
if (keyTable.size() == capacity) {
Node node = freqTable.get(minfreq).getLast();
keyTable.remove(node.key);
freqTable.get(minfreq).removeLast();
if (freqTable.get(minfreq).isEmpty()) {
freqTable.remove(minfreq);
}
}
minfreq = 1;
update(key,value,minfreq);
} else {
// 更新
Node node = keyTable.get(key);
int freq = node.freq;
freqTable.get(freq).remove(node);
if (freqTable.get(freq).isEmpty()) {
freqTable.remove(freq);
if (minfreq == freq) {minfreq += 1;}
}
update(key,value,freq + 1);
}
}
}
/**
* 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);
*/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
