牛牛的门票缓存系统_牛客题霸

动物园的门票售卖处需要一个缓存系统来管理门票信息。请你设计并实现一个满足 LFU（最不经常使用）缓存约束的数据结构。你需要实现一个类 TicketCache，其中包含以下方法： TicketCache(int capacity)：构造方法初始化 LFU 缓存，其中 capacity 是缓存的容量。 int getTicket(int ticketId)：如果门票编号 ticketId 存在于缓存中，则返回门票的信息 ticketInfo，否则返回 -1。 void putTicket(int ticketId, int ticketInfo)：如果门票编号 ticketId 已经存在于缓存中，则更新门票的信息为 ticketInfo；如果不存在，则向缓存中插入该门票编号和信息。如果插入操作导致缓存中门票数量超过容量 capacity，则应该逐出最不经常使用的门票。函数 getTicket 和 putTicket 必须以平均时间复杂度 O(1) 运行。

示例1

输入

["putTicket","putTicket","getTicket","putTicket","getTicket","putTicket","getTicket","getTicket","getTicket"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2

输出

[1,-1,1,-1,4]

说明

TicketCache ticketCache = new TicketCache(2);ticketCache.putTicket(1, 1);   // 缓存是 {1=1}ticketCache.putTicket(2, 2);   // 缓存是 {1=1, 2=2}ticketCache.getTicket(1);      // 返回 1ticketCache.putTicket(3, 3);   // 该操作会使得门票 2 作废，缓存是 {1=1, 3=3}ticketCache.getTicket(2);      // 返回 -1 (未找到)ticketCache.putTicket(4, 4);   // 该操作会使得门票 3 作废，缓存是 {4=4, 1=1}ticketCache.getTicket(1);      // 返回 1 (未找到)ticketCache.getTicket(3);      // 返回 -1
ticketCache.getTicket(4);      // 返回 4

备注:

1 0 0 最多调用 2 * 10^5 次 getTicket 和 putTicket 方法operations为操作数组，包含两种操作字符串data为数据数组，put操作时，有门票编号 ticketId 和门票的信息 ticketInfo两个元素，get操作时只有门票编号 ticketId 一个元素