leetcode - 460. LFU 缓存

题目

代码

#include <iostream>
#include <set>
#include <map> 
using namespace std;

struct Node{
    
	int cnt, time, key, value;
	bool operator < (const Node& rhs) const {
    
        return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
    }
};

int capacity, time;
map<int, Node> table;
set<Node> s;


LFUCache(int _capacity) {
    
	capacity = _capacity;
	time = 0;
	table.clear();
	s.clear();
}
    
int get(int key) {
    
	if(capacity == 0){
    
		return -1;
	}
	if(table.find(key) == table.end()){
    
		return -1;
	}
	Node node = table[key];
	s.erase(node);
	node.cnt += 1;
	node.time = ++time;
	s.insert(node);
	table[key] = node;
	return node.value; 
}
    
void put(int key, int value) {
    
	if(capacity == 0){
    
		return;
	}
	if(table.find(key) == table.end()){
    
		if(s.size() == capacity){
    
			table.erase(s.begin()->key);
			s.erase(s.begin());
		}
		Node node;
		node.key = key;
		node.value = value;
		node.cnt = 1;
		node.time = ++time;
		table[key] = node;
		s.insert(node);
	}else{
    
		Node node = table[key];
		s.erase(node);
		node.cnt += 1;
		node.time = ++time;
		node.value = value;
		s.insert(node);
		table[key] = node;
	}
}