一、题目
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2cs0TPR9UNJRkT1MGVOBDOsJGcohVYsR2MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLjJWN5ATOyMmZ4ImYhNWOiBzMmRzYjljNiVmMmN2NwQ2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
二、思路
1、自定义结构体存储信息,set+哈希表实现
2、set利用函数对象自定义排序规则
三、代码
struct Node
{
int keys;
int values;
int val;
int time;
};
class cmp
{
public:
bool operator()(const Node &a, const Node &b)
{
if (a.val != b.val)
{
return a.val < b.val;
}
return (a.time < b.time);
}
};
class Solution
{
public:
/**
* lfu design
* @param operators int整型vector<vector<>> ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> res;
vector<int> LFU(vector<vector<int>> &operators, int k)
{
if (operators.empty())
{
return res;
}
size = k;
for (int i = 0; i < operators.size(); ++i)
{
if (operators[i][0] == 1)
{
put(operators[i][1], operators[i][2]);
}
else if (operators[i][0] == 2)
{
get(operators[i][1]);
}
}
return res;
}
int get(int key)
{
if (Dic.count(key) == 0)
{
res.emplace_back(-1);
return -1;
}
Set.erase(Dic[key]);
Dic[key].val++;
Dic[key].time = num++;
Set.emplace(Dic[key]);
res.emplace_back(Dic[key].values);
return Dic[key].values;
}
void put(int key, int value)
{
Node node;
node.keys = key;
node.values = value;
node.time = num++;
if (Dic.count(key) == 0)
{
node.val = 1;
if (Set.size() < size)
{
Set.emplace(node);
Dic.emplace(key, node);
return;
}
Dic.erase(Set.begin()->keys);
Set.erase(Set.begin());
Set.emplace(node);
Dic.emplace(key, node);
return;
}
node.val = Dic[key].val + 1;
Set.erase(Dic[key]);
Set.emplace(node);
Dic[key] = node;
}
private:
set<Node, cmp> Set;
unordered_map<int, Node> Dic;
int num;
int size;
};