怎么操作到期时间数据结构

最近老是有朋友来问我，怎么操作到期时间数据结构？爱站技术小编现在整理出了一份资料供大家参考参考，有需要的朋友点进来看，希望能帮助到大家。

问题描述

在最近的一次编码采访中，我被要求实现一个密钥-值存储数据结构。实施

size（）：列表中的元素数。

find（key）：返回键处的值，否则抛出nosuchelement异常。

insert（key，timestamp）：使用此键添加或更新元素。如果列表已满，则什么也不要做。

• 列表具有可容纳的最大元素数量
• 每个元素都作为键和值插入，其后的持续时间不应视为列表中的时间，以及输入该元素的时间的时间戳。
• 如果列表已满，则忽略试图添加的元素，除非它是重复的键。
• 如果已经存在具有相同键的元素，则更新现有值和现有时间戳记
• 一旦时间超过元素的时间戳+持续时间，那么就不再将其视为结构的一部分。这意味着，如果列表先前已满，则列表不再完整。

我很难找到一种有效的方法来跟踪仍在列表中的元素，因为考虑到如果元素用完了，可以将其从列表中弹出。

思路：

我认为您正在寻找的是索引优先级队列。基本上，您将建立一个最小优先级队列，其键为时间戳。然后，您将创建一个索引（按键）来跟踪优先级队列中的项目位置。

在每次操作中，您都可以使用以下方法从队列中删除过期的项目：

while (pq.peek().timestamp 

其复杂度为O（k log n），其中k是要删除的项目数，n是队列中项目的总数。

http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html处有一个索引优先级队列实现。我听说过有关它的好消息，但我自己从未使用过它。

以上内容就是爱站技术频道小编为大家分享的怎么操作到期时间数据结构，看完以上分享之后，大家应该都知道怎么操作了吧。