算法 : Remember the last n unique numbers, 按顺序

Question

我想按顺序记住最后 n 个唯一数字。

我的意思是:假设 n = 4。

我当前的列表是 5 3 4 2 如果我加 6，它会变成 3 4 2 6。如果我改为添加 3，列表将变成 5 4 2 3，其中 3 移到前面。

我会这样做:将数字存储在队列中。添加新号码时，在队列中搜索该号码。如果没有找到号码，则在末尾弹出号码，并在前面压入新号码。如果找到该号码，则删除该位置的号码，然后将新号码推到前面。

很明显，从队列中的任意位置删除一个数字，优化队列操作(如 C++ 中的 std::deque)会非常慢。使用链接列表，虽然在列表中搜索会更慢。是否有更好的算法+数据结构组合来完成此类任务？

如果有什么不同的话，我不一定关心“按顺序记住最后 n 个唯一数字”。我特别需要知道，添加后从列表中删除了哪些元素(如果有)。

Answer 1

您可以使用双向链表。您可以将要记住的 n 个数字添加到哈希表中，其中键是数字本身，值是指向包含该数字的链表节点的指针。

然后在您描述的步骤中在队列中搜索号码您将其更改为查看号码是否在哈希表中这将是常数时间而不是使用队列的类轮时间。

如果您存储指向双向链表第一个元素的指针 p 和指向列表最后一个元素的指针 q，则您描述的 pop 和 push 操作可以在常数时间内执行。

你的步骤如果找到数字，删除那个位置的数字可以在恒定时间内执行，因为你已经有了要删除的数字的位置。(我的位置是指指针你从哈希表中得到)。

更新:

请注意，您必须更新哈希表以相应地删除和添加新数字。