首页 > 试题广场 >

设计LFU缓存结构

[编程题]设计LFU缓存结构
  • 热度指数:23020 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
一个缓存结构需要实现如下功能。
  • set(key, value):将记录(key, value)插入该结构
  • get(key):返回key对应的value值
但是缓存结构中最多放K条记录,如果新的第K+1条记录要加入,就需要根据策略删掉一条记录,然后才能把新记录加入。这个策略为:在缓存结构的K条记录中,哪一个key从进入缓存结构的时刻开始,被调用set或者get的次数最少,就删掉这个key的记录;
如果调用次数最少的key有多个,上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构,K作为参数给出

数据范围:
要求:get和set的时间复杂度都是 ,空间复杂度是


若opt=1,接下来两个整数x, y,表示set(x, y)
若opt=2,接下来一个整数x,表示get(x),若x未出现过或已被移除,则返回-1

对于每个操作2,返回一个答案
示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3

输出

[4,-1]

说明

在执行"1 4 4"后,"1 1 1"被删除。因此第二次询问的答案为-1   

备注:

import java.util.*;


public class Solution {
   
    public int[] LFU (int[][] operators, int k) {
        // hashMap和priorityQueue保存,hashMap存调用次数和计时,priorityQueue排序
        HashMap<Integer,Node> count=new HashMap<>();//对key计数,key=operators[i][1],value=node node.count计数 node.time 计时
        HashMap<Integer,int[]> temp=new HashMap<>(); //保存key(operators[i][1])和operators[i]的映射,好方便找出value值
        PriorityQueue<Integer> minHeap=new PriorityQueue<>((o1,o2)->count.get(o1).count.equals(count.get(o2).count)?
            count.get(o1).time.compareTo(count.get(o2).time):count.get(o1).count.compareTo(count.get(o2).count));//优先队列,取count值较小的,count值一致时取time小的
        ArrayList<Integer> res=new ArrayList<>();
        int time=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                if(temp.size()==k){
                    int poll=minHeap.poll(); //把调用次数最少的poll掉
                    count.remove(poll);
                    temp.remove(poll);
                }
                //插入temp和count
                temp.put(operators[i][1],operators[i]);
                if(count.containsKey(operators[i][1])){
                    Node node=new Node(count.get(operators[i][1]).count+1,time++);
                    count.put(operators[i][1],node);
                    minHeap.remove(operators[i][1]);
                    minHeap.offer(operators[i][1]);
                }else{
                    Node node1=new Node(1,time++);
                    count.put(operators[i][1],node1);
                    minHeap.offer(operators[i][1]);
                }
            }else if(operators[i][0]==2){
                if(temp.get(operators[i][1])==null){
                    res.add(-1);
                }else{
                    int[] operator=temp.get(operators[i][1]);
                    res.add(operator[2]);
                    if(count.containsKey(operators[i][1])){
                      Node node2=new Node(count.get(operators[i][1]).count+1,time++);
                    count.put(operators[i][1],node2);
                         minHeap.remove(operators[i][1]);
                        minHeap.offer(operators[i][1]);
                    }else{  
                        Node node3=new Node(1,time++);
                        count.put(operators[i][1],node3);
                        minHeap.offer(operators[i][1]);
                    }
                    
                }
            }
        }
        int[] result=new int[res.size()];
        for(int i=0;i<res.size();i++){
            result[i]=res.get(i);
        }
        return result;
    }
}

class Node{
    public Integer count;
    public Integer time;
    
    public Node(Integer count,Integer time){
        this.count=count;
        this.time=time;
    }
}


编辑于 2021-04-14 12:30:06 回复(0)
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Node:
    def __init__(self, key=-1, val=-1):
        self.key = key
        self.val = val
        self.freq = 1
        self.prev = None
        self.next = None

class DLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next = node
        node.next.prev = node
        self.size += 1

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

from collections import defaultdict
class LFUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.freq = defaultdict(DLinkedList)
        self.size = 0
        self.capacity = capacity
        self.min_freq = 0

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self.freq[node.freq].removeNode(node)
            if self.min_freq == node.freq and self.freq[node.freq].size == 0:
                self.min_freq += 1
            node.freq += 1
            self.freq[node.freq].addToHead(node)  
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self.freq[node.freq].removeNode(node)
            if self.min_freq == node.freq and self.freq[node.freq].size == 0:
                self.min_freq += 1
            node.freq += 1
            self.freq[node.freq].addToHead(node)
        else:
            self.size += 1
            if self.size > self.capacity:
                node = self.freq[self.min_freq].removeTail()
                self.cache.pop(node.key)
                self.size -= 1
            node = Node(key, value)
            self.cache[key] = node
            self.freq[1].addToHead(node)
            self.min_freq = 1




class Solution:
    def LFU(self , operators , k ):
        # write code here
        LFU = LFUCache(k)
        ret = []
        for operator in operators:
            if operator[0] == 1:
                LFU.put(operator[1], operator[2])
            else:
                ret.append(LFU.get(operator[1]))
        return ret

为什么超时了
编辑于 2021-04-23 12:09:45 回复(0)
继看了很多遍题解+调试了半天后终于过了……
struct Node
{
    int key;
    int value;
    Node* pre;
    Node* next;
    int fre;
    Node(int k,int v):key(k),value(v){
        fre=0;
        pre=nullptr;
        next=nullptr;
    }
};
class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    map<int,Node*> k_Node; //key-Node之间的映射
    map<int,Node*> fre_fNode; //频率-该频率对应的链表头结点 之间的映射
    
    int max_fre=0; //当前最大频率
    vector<int> LFU(vector<vector<int> >& operators, int K) {
        if(K==0) {
            return vector<int>();
        }
        vector<int> res;
        int len=0; //当前记录数
        for(vector<int> op:operators) {
            if(op[0]==2) {
                if(k_Node.count(op[1])==0) { //查询的点不存在
                    res.push_back(-1);
                } else { //查询点存在
                    Node* cur=k_Node[op[1]];
                    res.push_back(cur->value);
                    Dele(cur); //将cur从原有的fre链表中删除
                    (cur->fre)++; //调用次数+1
                    Add(cur); //调整该节点,将该节点插入新的频率链表中的位置
                }
            } else {
                //set操作
                int key=op[1],val=op[2];
                Node* cur;
                if(k_Node.count(key)) {
                    cur=k_Node[key];
                    cur->value=val;
                    Dele(cur); //将cur从原有的fre链表中删除
                } else{
                    //该点原来不存在,需要插入
                    if(len==K) {
                        //需删除一条记录
                        int i=1;
                        while(i<=max_fre && fre_fNode[i]->next==fre_fNode[i]) {
                            //因为频率是从1递增的,所以应该是连续的,直接从1开始查找
                            //跳过只有头结点的链表(为空)
                            i++;
                        }
                        Node *del=fre_fNode[i]->next;
                        fre_fNode[i]->next=del->next;
                        del->next->pre=fre_fNode[i];
                        k_Node.erase(del->key);
                        delete del;
                        len--;
                    }
                    cur=new Node(key,val);
                    len++;
                    k_Node[key]=cur;
                }
                (cur->fre)++; //调用次数+1
                 Add(cur); //因为调用次数增加,需要调整在链表中的位置
            }
        }
        return res;
    }
    void Dele(Node* cur) {
        cur->next->pre=cur->pre;
        cur->pre->next=cur->next;
    }
    void Add(Node* cur) {
        if(max_fre<cur->fre) {
            Node* newHead=new Node(0,0);
            newHead->next=newHead;
            newHead->pre=newHead;//生成表示新的频率的双向循环链表头结点
            max_fre++;
            fre_fNode[max_fre]=newHead;
        }
        //加入到新的频率的链表中
        Node *head=fre_fNode[cur->fre];
        cur->pre=head->pre;
        cur->next=head;
        cur->pre->next=cur;
        head->pre=cur;
    }
};


发表于 2021-04-19 11:54:43 回复(3)
import java.util.*;

class Node{
    int k;
    int v;
    int freq;
    Node(int k,int v,int freq){
        this.k = k;
        this.v =v;
        this.freq = freq;
    }
}

class LFUCache {
    HashMap<Integer,Node> hash;
    // 每个链表头部是当前频率最先淘汰的节点,
    HashMap<Integer,LinkedList<Node>> freq_hash;   // key是出现频率,value是双向链表
    int capacity;
    int min_f;                                    // 最小的频率
    int size;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        hash = new HashMap<Integer,Node>();
        freq_hash = new HashMap<Integer,LinkedList<Node>>();
        min_f = 1;
        size = 0;

    }

    public int get(int key) {
        if(hash.get(key) != null){
            Node past = hash.get(key);
            Node newNode = new Node(key,past.v,past.freq+1);
            hash.replace(key,newNode);
            freq_hash.get(past.freq).remove(past);
            if(freq_hash.get(past.freq).size() == 0){
                freq_hash.remove(past.freq);
                if(min_f == past.freq)
                    ++min_f;
            }
            if(freq_hash.get(newNode.freq) == null){
                freq_hash.put(newNode.freq,new LinkedList<>());
            }
            freq_hash.get(newNode.freq).addLast(newNode);
            return past.v;
        }else
            return -1;

    }

    public void put(int key, int value) {
        if(capacity == 0)
            return;
        if(hash.get(key) == null){
            Node newNode = new Node(key,value,1);
            if(size == capacity){
                Node rm = freq_hash.get(min_f).removeFirst();
                if(freq_hash.get(min_f).size() == 0)
                    freq_hash.remove(min_f);
                hash.remove(rm.k);
                --size;
            }
            hash.put(key,newNode);
            if(freq_hash.get(1) == null){
                freq_hash.put(1,new LinkedList<>());
            }
            freq_hash.get(1).addLast(newNode);
            ++size;
            min_f = 1;
        }else{
            Node past = hash.get(key);
            Node newNode = new Node(key,value,past.freq+1);

            hash.replace(key,newNode);

            freq_hash.get(past.freq).remove(past);
            if(freq_hash.get(past.freq).size() == 0){
                freq_hash.remove(past.freq);
                if(min_f == past.freq)
                    ++min_f;
            }
            if(freq_hash.get(newNode.freq) == null){
                freq_hash.put(newNode.freq,new LinkedList<>());
            }
            freq_hash.get(newNode.freq).addLast(newNode);
        }
    }
}

public class Solution {
    
    public int[] LFU (int[][] operators, int k) {
        LFUCache lfu = new LFUCache(k);
        ArrayList<Integer> data = new  ArrayList<Integer>();
        int row = operators.length;
        for(int i = 0;i < row;++i){
            int op = operators[i][0];
            int key = operators[i][1];
            if(op == 1)
                lfu.put(key,operators[i][2]);
            if(op == 2)
                data.add(lfu.get(key));
        }
        int [] res = new int[data.size()];
        for(int i = 0;i < data.size();++i)
            res[i] = data.get(i);
        return res;
        
        
    }
}

发表于 2021-04-04 11:07:43 回复(0)
1. 用一个unordered_map作为缓存,用来判断key在不在缓存里面
2. 用一个std::set对缓存中的所有元素按照访问频率、访问时间从小到达排序,因为std::set的底层是红黑树结构,是一个有序的数据结构
3. 需要注意的是在定义set的排序函数,operator<必须被重载为const类型
#include <unordered_map>

struct Node {
    int key, value;
    int frequency, visit_time;
    Node() { }
    Node(int k, int v, int f, int t): key(k), value(v), frequency(f), visit_time(t) { }
    
    // (*this).operator<(node)相当于operator<((*this), node)
    bool operator<(const Node& node) const{
        if(this->frequency == node.frequency) {
            return this->visit_time < node.visit_time;
        }
        else {
            return this->frequency < node.frequency;
        }
    }
};

class Solution {
public:
    int sys_time;            // 代表系统时间
    int capacity;            // 代表缓存容量
    std::set<Node> sorted_tree;
    std::unordered_map<int, Node> cache;
    
    void init(int _capacity) {
        sys_time = 0;
        capacity = _capacity;
    }
    
    int get(int key) {
        sys_time++;
        if(capacity == 0) {
            return -1;
        }
        auto it = cache.find(key);
        if(it == cache.end()) {
            return -1;
        }
        Node node = it->second;
        // 从set中删除该结点
        sorted_tree.erase(node);
        
        node.visit_time = sys_time;    // 修改访问时间
        node.frequency++;              // 修改访问次数
        
        cache[key] = node;
        sorted_tree.insert(node);
        
        return node.value;
    }
    
    void set(int key, int value) {
        sys_time++;
        if(capacity == 0) {
            return;
        }
        auto it = cache.find(key);
        if(it == cache.end()) {
            // 缓存已满,需要删除最少被访问的元素
            if(cache.size() == capacity) {
                auto delNode = sorted_tree.begin();
                cache.erase(delNode->key);
                sorted_tree.erase(delNode);
            }
            Node newNode(key, value, 1, sys_time);
            cache[key] = newNode;
            sorted_tree.insert(newNode);
        }
        else {
            Node node = it->second;
            sorted_tree.erase(node);
            node.value = value;
            node.frequency++;
            node.visit_time = sys_time;
            cache[key] = node;
            sorted_tree.insert(node);
        }
    }
    
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        vector<int> ans;
        // 初始化
        init(k);
        
        for(auto& op: operators) {
            int operate = op[0];
            if(operate == 1) {
                set(op[1], op[2]);
            }
            else if(operate == 2) {
                ans.push_back(get(op[1]));
            }
            else {
                continue;
            }
        }
        return ans;
    }
};


发表于 2020-09-18 10:02:17 回复(3)
有点小复杂,用一个HashMap存储key和value。
import java.util.*;


public class Solution {
    class Node{
    int key;
    int value;
    int frep=1;
    public Node(){
    }
    public Node(int key,int value){
        this.key = key;
        this.value = value;
    }
  }
    Map<Integer,Node> cache;//存储数据
    Map<Integer, LinkedHashSet<Node>> freqMap;//存储频率对应的双向链表
    int size;//当前已经存储的数据个数
    int capacity;//存储容量
    int min;//当前最小的频率
        
        
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        this.capacity = k;
        cache = new HashMap<>();
        freqMap = new HashMap<>();
        
        List<Integer> out = new ArrayList<>();
        for(int i=0;i < operators.length;i++){
            if(operators[i][0] == 1){
                put(operators[i][1],operators[i][2]);
            }
            else if(operators[i][0] == 2){
                out.add(get(operators[i][1]));
            }
        }
        int[] res = new int[out.size()];
        for(int i=0;i < out.size();i++){
            res[i] = out.get(i);
        }
        return res;
    }
        //get函数,先获取节点,如果节点为空,则返回-1,不为空则更新频率再返回节点值
    public int get(int key){
        Node node = cache.get(key);
        if(node == null){
            return -1;
        }
        freqInc(node);
        return node.value;
    }
    //put函数
    public void put(int key,int value){
        if(capacity == 0) return;
        Node node = cache.get(key);
        if(node != null){
            node.value = value;
            freqInc(node);
        }
        else {
            //如果当前存储满了,就删除一个节点
            if(size == capacity){
                Node deadNode = removeNode();
                cache.remove(deadNode.key);
                size--;
            }
            //添加新的节点
            node = new Node(key,value);
            cache.put(key,node);//节点加入存储的hashmap
            addNode(node);
            size++;//更新当前存储容量
        }
    }
    //更新频率函数
    public void freqInc(Node node){
        //将节点从原频率的链表中删除,并更新当前最小的频率
        int frep = node.frep;
        LinkedHashSet<Node> set = freqMap.get(frep);
        set.remove(node);
        //如果当前频率是最小频率,并且移除该节点后,最小频率的链表为空则更新最小频率,为当前频率加一
        if(frep == min && set.size() == 0){
            min = frep + 1;
        }
        //更新节点的频率,并且加入到对应的频率链表
        node.frep++;
        LinkedHashSet<Node> newSet = freqMap.computeIfAbsent(frep + 1, k -> new LinkedHashSet<>());
        //如果不存在当前频率对应的频率链表,则新建一个
        newSet.add(node);
    }
    //在链表中删除节点函数,删除频率最小,并且最久没使用的节点
    public Node removeNode(){
        LinkedHashSet<Node> set = freqMap.get(min);
        Node deadNode = set.iterator().next();//删除set中的第一个元素,就是最先加入的那个
        set.remove(deadNode);
        return deadNode;
    }
    //在链表中添加节点函数
    public void addNode(Node node){
        LinkedHashSet<Node> set = freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>());
        set.add(node);
        min = 1;//只要添加了新节点最小频率就是1,min变化还会发生在更新频率的时候
    }
}


发表于 2020-08-31 17:52:17 回复(1)
纯Map实现(纯粹是因为链表太长了不想看),在LRU的基础上改的,仅供参考。
/**
 * @param {number} capacity
 */
var Solution = function(capacity) {
    // write code here
    this.max = capacity;
    this.map = new Map();//保存数据的map
    this.nummap = new Map();//记录次数的map
};

/** 
 * @param {number} key
 * @return {number}
 */
Solution.prototype.get = function(key) {
    // write code here
    if(!this.map.has(key)) return -1;
    else {
        let value = this.map.get(key);
        let cnt = this.nummap.get(key)+1;
        //每访问一次重新加入,方便后续次数相同的情况找到最早访问的
        this.nummap.delete(key);
        this.nummap.set(key,cnt);
        return value;
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
Solution.prototype.set = function(key, value) {
    // write code here
    if(this.map.has(key)){
        this.map.set(key,value);
        this.nummap.set(key,this.nummap.has(key)?this.nummap.get(key)+1:1);
     }
    else{
        if(this.map.size == this.max){
            let keys = Array.from(this.nummap.keys());
            let cnt = Infinity,tmp;
            //找到次数最小并且访问最早的
            for(let item of keys){
                if(this.nummap.get(item)<cnt){cnt=this.nummap.get(item);tmp=item;}
            }
            //同时删掉两个map中该key的数据
            this.map.delete(tmp);
            this.nummap.delete(tmp);
            
            this.map.set(key,value);
            this.nummap.set(key,this.nummap.has(key)?this.nummap.get(key)+1:1);
        }else{
            this.map.set(key,value);
            this.nummap.set(key,this.nummap.has(key)?this.nummap.get(key)+1:1);
        }
    }
};

/**
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LFU( operators ,  k ) {
    // write code here
    let obj = new Solution(k);
    let res = [];
    for(let i=0;i<operators.length;i++){
        let op = operators[i];
        //进行set
        if(op[0]==1){
            obj.set(op[1],op[2]);
        }
        //进行get
        else{
            res.push(obj.get(op[1]));
        }
    }
    return res;
}
module.exports = {
    LFU : LFU
};



发表于 2022-10-30 19:11:04 回复(1)
用调表更好,但是写调表要花好多时间,就用tree map吧。。
#include <algorithm>
#include <map>
#include <unordered_map>
struct Node {
    int key;
    int data;
    int accessCount{};
    Node* prev{};
    Node* next{};
    Node(int key, int data) : key(key), data(data) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        this->cap = k;
        vector<int> result;
        for (auto const &item : operators) {
            if (item[0] == 1) {
                set(item[1], item[2]);
            } else if (item[0] == 2) {
                result.push_back(get(item[1]));
            }
        }

        return result;
    }

    void set(int key, int data) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            auto *node = it->second;
            if (node->data != data) {
                node->data = data;
            }
            removeFromLFU(node);
            node->accessCount += 1;
            addToLFU(node);
            return;
        }

        if (cache.size() >= cap) {
            auto *rmNode = removeCandidate();
            cache.erase(rmNode->key);
            delete rmNode;
        }

        auto *node = new Node(key, data);
        cache[key] = node;
        node->accessCount += 1;
        addToLFU(node);
    }

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;
        }

        auto *node = it->second;
        removeFromLFU(node);
        node->accessCount += 1;
        addToLFU(node);

        return node->data;
    }

    Node* removeFromLFU(Node *node) {
        auto it = lfuCache.find(node->accessCount);
        assert(it != lfuCache.end());
        return removeFromLFU(it, node);
    }

    Node* removeFromLFU(map<int, pair<Node*, Node*>>::iterator &it, Node *node) {
        auto *prev = node->prev;
        auto *next = node->next;
        if (prev != nullptr) {
            prev->next = next;
        } else {
            it->second.first = next;
        }
        if (next != nullptr) {
            next->prev = prev;
        } else {
            it->second.second = prev;
        }

        if (it->second.first == nullptr) {
            lfuCache.erase(it->first);
        }

        node->prev = node->next = nullptr;
        return node;
    }

    void addToLFU(Node *node) {
        auto it = lfuCache.find(node->accessCount);
        if (it == lfuCache.end()) {
            //lfuCache.emplace(make_pair(node->accessCount, make_pair(node, node)));
            lfuCache[node->accessCount] = make_pair(node, node);
            return;
        }

        node->next = it->second.first;
        it->second.first->prev = node;
        it->second.first = node;
    }

    Node* removeCandidate() {
        auto it = lfuCache.lower_bound(INT_MIN);
        assert(it != lfuCache.end());
        auto *node = removeFromLFU(it, it->second.second);
        return node;
    }

    int cap;
    unordered_map<int, Node*> cache;
    map<int, pair<Node*, Node*>> lfuCache; // a skip-list should be better, but coding for a skip-list takes lots of time
};


发表于 2023-09-22 18:13:27 回复(0)
设计一个LFUCache类用于实现set和get操作,在LFUCache类内使用两个unordered_map,使得set和get操作的时间复杂度为O(1),具体代码如下:
class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        if (!keyToIdx.count(key)) return -1;

        /*更新freToKey*/
        int fre = keyToIdx[key]->fre;
        int val = keyToIdx[key]->val;
        // 1. 删除原结点
        freToKey[fre].erase(keyToIdx[key]);
        if (freToKey[fre].empty()) freToKey.erase(fre);
        if (minFre == fre && !freToKey.count(fre)) {
            minFre = fre + 1;
        }
        // 2. 增加结点
        freToKey[fre + 1].push_front(Node(key, val, fre + 1));
        // 3. 重新修改指向
        keyToIdx[key] = freToKey[fre + 1].begin();

        // 返回
        return val;
    }

    void set(int key, int value) {
        if (cap == 0) return;

        // LFU缓存中已存在key
        if (keyToIdx.count(key)) {
            get(key);
            keyToIdx[key]->val = value;
            return;
        }

        if (keyToIdx.size() == cap) {
            // LFU缓存容量满,删除频率最小的结点
            int k = freToKey[minFre].back().key;
            freToKey[minFre].pop_back();
            if (freToKey[minFre].empty()) freToKey.erase(minFre);

            keyToIdx.erase(k);
        }
        // 插入新结点
        freToKey[1].push_front(Node(key, value, 1));
        keyToIdx[key] = freToKey[1].begin();
        minFre = 1;
    }

private:
    struct Node {
        int key, val, fre;
        Node() = default;
        Node(int k, int v, int f): key(k), val(v), fre(f){}
    };
    int cap, minFre;
    unordered_map<int, list<Node>::iterator> keyToIdx;
    unordered_map<int, list<Node>> freToKey;
};


class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        LFUCache lfu(k);
        vector<int> ans;
        for (auto & it : operators) {
            if (it[0] == 1) {
                lfu.set(it[1], it[2]);
            } else {
                ans.push_back(lfu.get(it[1]));
            }
        }
        
        return ans;
    }
};


发表于 2022-05-02 11:45:40 回复(0)
class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    template<class T>
    class Priority{
        public:
        priority_queue<T,vector<T>,greater<T>>  g_q;
        priority_queue<T,vector<T>,greater<T>>  l_q;
        void push(T a){
            g_q.push(a);
        }
        void erase(T b){
            l_q.push(b);
        }
        T top(){
             while(l_q.size()&& g_q.size()&&l_q.top()<=g_q.top()){
                if(l_q.top()==g_q.top()){
                    g_q.pop();
                }
                l_q.pop();
            }
            return g_q.top();
        }
        void pop(){
           while(l_q.size()&& g_q.size()&&l_q.top()<=g_q.top()){
                if(l_q.top()==g_q.top()){
                    g_q.pop();
                }
                l_q.pop();
            }
            g_q.pop();
        }

    };
    class LFU_ {
        public:
        Priority<pair<pair<int,int>,pair<int,int>>>  q;
        unordered_map<int ,pair<pair<int,int>,pair<int,int>>> m;
        int size;
        LFU_(int s):size(s){

        };
        int time=0;
        int get(int x){
            if(m.find(x)==m.end()){
                return -1;
            }
            else{
                auto &p=m[x];
                q.erase(p);
                p.first.first+=1;
                p.first.second=time++;
                q.push(p);
                return p.second.second;
            }
        }
        void set(int x,int y){
            if(m.find(x)==m.end()){
               if(size==0){
                   auto p=q.top();
                   q.pop();
                   m.erase(p.second.first);
                   pair<pair<int,int>,pair<int,int>> b={{0,time++},{x,y}};
                   m[x]=b;
                   q.push(b);
               }
               else{
                   pair<pair<int,int>,pair<int,int>> b={{0,time++},{x,y}};
                   m[x]=b;
                   q.push(b);
                   size--;
               }
            }else{
                auto &p=m[x];
                q.erase(p);
                p.first.first+=1;
                p.first.second=time++;
                p.second.second=y;
                q.push(p);
            }
        }
    };
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        LFU_ tmp(k);
        vector<int> out;
        for(auto i:operators){
            if(i[0]==1){
                tmp.set(i[1],i[2]);
            }
            else{
                int o=tmp.get(i[1]);
                out.push_back(o);
            }
        }
        return out;
    }
    
    

};
使用两个优先队列实现插入和删除
发表于 2022-04-16 19:48:03 回复(0)
用一个 LinkedHashMap进行保存, key为待存数据key, value整型数组 为  值和出现次数
import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        Map<Integer, Integer[]> map = new LinkedHashMap<>(k);
        List<Integer> res = new ArrayList<>();
        for(int [] ops: operators) {
            if(ops[0] == 1) {
                // set
                set(map, ops[1], ops[2], k);
            }else if(ops[0] == 2) {
                // get
                res.add(get(map, ops[1]));
            }
        }
        
        return res.stream().mapToInt(x -> x).toArray();
    }
    
    // set
    private void set(Map<Integer, Integer[]> map, int key, int val, int cap) {
        if(map.size() == cap) {
            remove(map);
        }
        Integer[] value = map.get(key);
        if(value != null) {
            // exists
            map.put(key, new Integer[]{val, value[1] + 1});
        }else {
            map.put(key, new Integer[]{val, 1});
        }
    }
    
    // get
    private Integer get(Map<Integer, Integer[]> map, int key) {
        Integer[] value = map.get(key);
        if(value == null) {
            return -1;
        }else {
            map.put(key, new Integer[]{value[0], value[1] + 1});
            return value[0];
        }
    }
    
    // remove
    private void remove(Map<Integer, Integer[]> map) {
        int key = 0,  min = Integer.MAX_VALUE;
        for(Map.Entry<Integer, Integer[]> entry: map.entrySet()) {
            if(entry.getValue()[1] < min) {
                min = entry.getValue()[1];
                key = entry.getKey();
            }
        }
        map.remove(key);
    }
}


编辑于 2021-03-23 17:02:07 回复(0)
#include <mutex>
#include <unordered_map>
#include <vector>


class Solution {
  public:
    struct Node {
        int key, val;
        Node* pre, *next;
        Node(): key(0), val(0), pre(nullptr), next(nullptr) {};
        Node(int k, int v): key(k), val(v), pre(nullptr), next(nullptr) {};
    };
    unordered_map<int, Node*> hash;
    

    void removeNode(Node* node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    void insertNode(Node* node,Node* head,Node* tail) {
        node->next=head->next;
        head->next->pre=node;
        head->next=node;
        node->pre=head;
    }

    vector<int> LFU(vector<vector<int> >& operators, int cap) {
       Node* head=new Node();
       Node* tail=new Node();
       head->next=tail;
       tail->pre=head;
       int size=0;
       vector<int>ans;
        for (int i = 0; i < operators.size(); i++) {
            int key = operators[i][1], val = operators[i][2];
            if (operators[i][0] == 1) {
                if (hash.count(key)) {
                    Node* node = hash[key];
                    node->val = val;
                    hash[key] = node;
                    removeNode(node);
                    insertNode(node,head,tail);
                }else{
                    if(cap==size){
                        hash.erase(tail->pre->key);
                        removeNode(tail->pre);
                        size--;
                    }
                    Node* node=new Node(key,val);
                    hash[key]=node;
                    insertNode(node, head, tail);
                    size++;
                }
            }
            if(operators[i][0]==2){
                if(!hash.count(key)){
                    ans.push_back(-1);
                }else{
                    Node* node=hash[key];
                    ans.push_back(node->val);
                    removeNode(node);
                    insertNode(node, head, tail);
                }
            }
        }
        return ans;
    }
};

编辑于 2024-03-28 17:28:06 回复(0)

加上最近访问会超时,不加倒数第二个用例过不去,求大佬优化一下循环,或者加一个最近访问的标记。

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        buf = []
        res = []
        for i in operators:
            if i[0] == 1:  # opt=1插入数据
                if i[1] in [j[0] for j in buf]:  # 如果插入数据在缓存里
                    for j in buf:
                        if j[0] == i[1]:  # 找到该数据
                            j[1] = i[2]  # 更新value
                            j[2] += 1  # 访问次数+1
                    # # 调整为最近访问
                    # for j in buf:
                    #     if j[0] == i[1]:
                    #         buf.remove(j)
                    #         buf.append(j)

                else:  # 插入数据不在缓存里
                    if len(buf) >= k:  # 已经存满
                        minfw = min([j[2] for j in buf])  # 找到访问次数最少的
                        for j in buf:
                            if j[2] == minfw:  # 更新插入数据
                                j[0] = i[1]  # 更新key
                                j[1] = i[2]  # 更新value
                                j[2] = 1  # 首次访问
                        # # 调整为最近访问
                        # for j in buf:
                        #     if j[0] == i[1]:
                        #         buf.remove(j)
                        #         buf.append(j)
                    else:  # 还没存满
                        buf.append([i[1], i[2], 1])

            else:  # opt=2访问数据
                if i[1] in [j[0] for j in buf]:  # get(x)在缓存里
                    for j in buf:
                        if j[0] == i[1]:  # 找到该数据
                            j[2] += 1  # 访问次数+1
                            res.append(j[1])
                else:
                    res.append(-1)

        return res
编辑于 2024-03-18 20:47:42 回复(0)
    public int[] LFU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> res=new ArrayList<>();
        Map<Integer,Integer> m1=new LinkedHashMap<>(); // 记录key value
        Map<Integer,Integer> m2=new LinkedHashMap<>(); // 记录key的先后及次数
        for(int i=0;i<operators.length;i++){
            int opt=operators[i][0];
            int key=operators[i][1];
            if(opt==1){
                int val=operators[i][2];
                if(m2.containsKey(key)){ // 写和读都要判断是否已存在
                    int cnt=m2.get(key)+1;
                    m2.remove(key);
                    m1.put(key,val);
                    m2.put(key,cnt);
                }else{
                    if(m1.size()==k){
                        Iterator<Map.Entry<Integer,Integer>> iter=m2.entrySet().iterator();
                        int cnt=Integer.MAX_VALUE ,dk=0;
                        while(iter.hasNext()){
                            Map.Entry<Integer,Integer> entry=iter.next();
                            if(entry.getValue()<cnt){
                                cnt=entry.getValue();
                                dk=entry.getKey();
                            }
                        }
                        m1.remove(dk);
                        m2.remove(dk);
                    }
                    m1.put(key,val);
                    m2.put(key,1);
                }
            }else{
                if(m2.containsKey(key)){
                    int cnt=m2.get(key)+1;
                    m2.remove(key);
                    m2.put(key,cnt);
                }
                res.add(m1.getOrDefault(key,-1));
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

发表于 2024-03-09 14:18:53 回复(0)

双哈希表

func LFU(operators [][]int, k int) []int {
    lfuCache, ans := NewLFUCache(k), []int{}
    for _, item := range operators {
        switch item[0] {
        case 1:
            lfuCache.Set(item[1], item[2])
        case 2:
            ans = append(ans, lfuCache.Get(item[1]))
        }
    }
    return ans
}

type LFUNode struct {
    key   int
    value int
    times int
    prev  *LFUNode
    next  *LFUNode
}

type LFUCache struct {
    mapOne   map[int]*LFUNode
    mapTwo   map[int][2]*LFUNode
    cap      int
    len      int
    minTimes int
}

func NewLFUCache(capacity int) *LFUCache {
    return &LFUCache{
        mapOne:   map[int]*LFUNode{},
        mapTwo:   map[int][2]*LFUNode{},
        cap:      capacity,
        len:      0,
        minTimes: -1,
    }
}

func (lfu *LFUCache) Get(key int) int {
    node, ok := lfu.mapOne[key]
    if !ok {
        return -1
    }
    lfu.delete(node)
    node.times++
    lfu.insert(node)

    return node.value
}

func (lfu *LFUCache) Set(key, value int) {
    if node, ok := lfu.mapOne[key]; ok {
        lfu.delete(node)
        node.value = value
        node.times++
        lfu.insert(node)
    } else {
        if lfu.len == lfu.cap {
            headTail := lfu.mapTwo[lfu.minTimes]
            delete(lfu.mapOne, headTail[1].prev.key)
            lfu.delete(headTail[1].prev)
            lfu.len--
        }
        node := &LFUNode{key: key, value: value, times: 1}
        lfu.mapOne[key] = node
        lfu.insert(node)
        lfu.minTimes = 1
        lfu.len++
    }
}

func (lfu *LFUCache) delete(node *LFUNode) {
    headTail := lfu.mapTwo[node.times]
    if node.prev == headTail[0] && node.next == headTail[1] && node.times == lfu.minTimes {
        lfu.minTimes++
    }
    node.prev.next, node.next.prev = node.next, node.prev
}

func (lfu *LFUCache) insert(node *LFUNode) {
    if headTail, ok := lfu.mapTwo[node.times]; ok {
        head := headTail[0]
        head.next, node.prev, node.next, head.next.prev = node, head, head.next, node
    } else {
        head, tail := &LFUNode{}, &LFUNode{}
        head.next, tail.prev = tail, head
        lfu.mapTwo[node.times] = [2]*LFUNode{head, tail}
        head.next, node.prev, node.next, head.next.prev = node, head, head.next, node
    }
}
编辑于 2024-01-31 02:32:20 回复(0)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LFU(operators, k) {
    // write code here
    const cache = new Map();
    const result = [];

    function get(key) {
        if (cache.has(key)) {
            const [value, count] = cache.get(key);
            cache.delete(key);
            cache.set(key, [value, count + 1]);
            result.push(value);
            return value;
        } else {
            result.push(-1);
            return -1;
        }
    }

    function set(key, value) {
        let count = 1;
        if (cache.has(key)) {
            count += cache.get(key)[1];
            cache.delete(key);
        }
        if (cache.size >= k) {
            const firstKey = cache.keys().next().value;
            const min = {
                key: firstKey,
                count: cache.get(firstKey)[1],
            };
            cache.forEach((item, key) => {
                const count = item[1];
                if (count < min.count) {
                    min.key = key;
                    min.count = count;
                }
            });
            cache.delete(min.key);
        }
        cache.set(key, [value, count]);
    }

    operators.forEach((item) => {
        const opt = item[0];
        if (opt === 1) {
            set(item[1], item[2]);
        }
        if (opt === 2) {
            get(item[1]);
        }
    });

    return result;
}


发表于 2023-11-14 18:27:05 回复(0)
public class Solution {

    private int capacity;

    private Map<Integer, Node> viewCache = new HashMap<>();

    private Map<Integer, Node> cache = new HashMap<>();

    private ArrayList<Integer> result = new ArrayList<>();

    private int minFreq = 1;

    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        this.capacity = k;
        for (int[] operator:operators) {
            handleOpt(operator);
        }
        return listToArray(result);
    }

    private void handleOpt(int[] operator) {
        int optType = operator[0];
        switch (optType) {
            case 1:
                set(operator[1], operator[2]);
                break;
            case 2:
                result.add(get(operator[1]));
                break;
        }
    }

    private int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        node.freq += 1;
        handleFreq(node);
        return node.value;
    }

    private void set(int key, int value) {
        Node node ;
        if (!cache.containsKey(key)) {
            checkSize();
            node = new Node (key, value);
            cache.put(key, node);
            minFreq = node.freq;
        } else {
            node = cache.get(key);
            node.value = value;
            node.freq += 1;
        }
        handleFreq(node);
    }

    private void handleFreq(Node node) {
        //浏览次数变更,节点去除(完成上下节点的交接,清除与上下节点的指向)
        clearPointer(node);
        //如果存在相同浏览次数的节点,放在节点尾部
        if (viewCache.containsKey(node.freq)) {
            Node head = viewCache.get(node.freq);
            while (head.next != null) {
                head = head.next;
            }
            head.next = node;
            node.pre = head;
            return;
        }
        //不存在这个浏览次数的节点,新建key
        viewCache.put(node.freq, node);
    }

    private void clearPointer(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        if (pre != null) {
            pre.next = next;
        }
        if (next != null) {
            next.pre = pre;
        }
        if (viewCache.get(node.freq - 1) == node) {
            if (next != null) {
                viewCache.put(node.freq - 1, next);
            } else {
                viewCache.remove(node.freq - 1);
                if (node.freq - 1 == minFreq) {
                    minFreq = node.freq;
                }
            }
        }
        node.next = null;
        node.pre = null;
    }

    private void checkSize() {
        if (cache.size() < capacity) {
            return;
        }
        Node node = viewCache.get(minFreq);
        int key = node.key;
        if (node.next != null) {
            node = node.next;
            node.pre = null;
            viewCache.put(minFreq, node);
        } else {
            viewCache.remove(minFreq);
            minFreq++;
        }
        cache.remove(key);
    }

    private int[] listToArray(ArrayList<Integer> list) {
        int[] output = new int[result.size()];
        for (int i = 0; i < list.size(); i++ ) {
            output[i] = list.get(i);
        }
        return output;
    }

    class Node {
        int key;
        int value;
        int freq;
        Node pre;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1;
        }
    }

}

发表于 2023-11-09 17:36:22 回复(0)
用map, set
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    set<pair<pair<int, int>, map<int, int>> >se;
    map<int, int>mp;
    unordered_map<int, int>tm;
    unordered_map<int, int>cnt;
    int c = 0;
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        for (auto& t : operators) {
            if (t[0] == 1) {
                int a = t[1], b = t[2];
                if (mp.find(a) != mp.end()) {
                    map<int, int> p;
                    p[a] = mp[a];
                    se.erase({{cnt[a], tm[a]}, p});
                }
                while (se.size() >= k) {
                    auto it = (*se.begin()).second.begin()->first;
                    mp.erase(it);
                    se.erase(se.begin());
                }
                mp[a] = b;
                tm[a] = c++;
                ++cnt[a];
                map<int, int> p;
                p[a] = b;
                se.insert({{cnt[a], tm[a]}, p});
            } else {
                int a = t[1];
                if (mp.find(a) == mp.end()) {
                    res.push_back(-1);
                    continue;
                }
                map<int, int> p;
                p[a] = mp[a];
                se.erase({{cnt[a], tm[a]}, p});

                res.push_back(mp[a]);
                tm[a] = c++;
                ++cnt[a];
                map<int, int> temp;
                temp[a] = mp[a];
                se.insert({{cnt[a], tm[a]}, temp});
            }
        }
        return res;
    }
};


发表于 2023-11-03 18:05:28 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # write code here
        dic_val = {}
        dic_num = {} #当前值的访问次数,和访问顺序 key->int: value->[次数,顺序]
        res = []
        for i, ope in enumerate(operators):

            if ope[0] == 1:
                if len(dic_val) == k:
                    if ope[1] not in dic_val.keys():
                        key = sorted(dic_num.items(), key=lambda x: (x[1][0], x[1][1]))
                        dic_num.pop(key[0][0])
                        dic_val.pop(key[0][0])
                dic_val[ope[1]] = ope[2]
               
                if ope[1] in dic_num.keys():
                    dic_num[ope[1]] = [dic_num[ope[1]][0] + 1, i]
                else:
                    dic_num[ope[1]] = [1, i]
            else:
                if  ope[1] in dic_val.keys():
                    res.append(dic_val[ope[1]] )
                    if ope[1] in dic_num.keys():
                        dic_num[ope[1]] = [dic_num[ope[1]][0] + 1, i]
                    else:
                        dic_num[ope[1]] = [1, i]
                else:
                    res.append(-1)

        return res

发表于 2023-10-07 15:25:34 回复(0)
class MyCompare
{
public:
	bool operator() (const pair<int, int> a, const pair<int, int> b) const {
		if (a.first < b.first) {
			return a.first < b.first;
		}
		else if (a.first > b.first) {
			return a.first < b.first;
		} 
		return a.second < b.second;
	}
};
class Solution {
public:
    int time = 0;
    map<int, pair<int, int>> mp1;
    map<pair<int, int>, int, MyCompare> mp2;
    map<int, int> mp3;
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> result;
        for (int i = 0; i < operators.size(); i++) {
            time++;
            if (operators[i][0] == 1)  { // set
                if (mp3.size() >= k) {
                    int keyt = mp2.begin()->second;
                    auto pairt = mp1[keyt];
                    mp1.erase(keyt);
                    mp2.erase(pairt);
                    mp3.erase(keyt);
                    if (mp3.find(operators[i][1]) != mp3.end()) {
                        mp3[operators[i][1]] = operators[i][2];
                        auto it = mp1[operators[i][1]];
                        mp1[operators[i][1]] = make_pair(it.first + 1, time + 1);
                        mp2.erase(it);
                        mp2.insert(make_pair(make_pair(it.first + 1, time + 1), operators[i][1]));
                    } else {
                        mp3.insert(make_pair(operators[i][1], operators[i][2]));
                        mp2.insert(make_pair(make_pair(1, time + 1), operators[i][1]));
                        mp1.insert(make_pair(operators[i][1], make_pair(1,  time + 1)));
                    }
                } else {
                    if (mp3.find(operators[i][1]) != mp3.end()) {
                        mp3[operators[i][1]] = operators[i][2];
                        auto pairt = mp1[operators[i][1]];
                        mp1[operators[i][1]] = make_pair(pairt.first + 1, time + 1);
                        mp2.erase(pairt);
                        mp2.insert(make_pair(make_pair(pairt.first + 1, time + 1), operators[i][1]));
                    } else {
                        mp3[operators[i][1]] = operators[i][2];
                        mp1.insert(make_pair(operators[i][1], make_pair(1, time + 1)));
                        mp2.insert(make_pair(make_pair(1, time + 1), operators[i][1]));
                    }
                }
            } else {   //get
                if (mp3.find(operators[i][1]) != mp3.end()) {
                    auto pairt = mp1[operators[i][1]];
                    mp1[operators[i][1]] = make_pair(pairt.first + 1, time + 1);
                    mp2.erase(pairt);
                    mp2.insert(make_pair(make_pair(pairt.first + 1, time + 1), operators[i][1]));
                    result.push_back(mp3[operators[i][1]]);
                } else {
                    result.push_back(-1);
                }
            }
        }
        return result;
    }
};

发表于 2023-08-17 18:50:21 回复(0)