algorithm - 算法：按顺序记住最后 n 个唯一数字

Question

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

这就是我的意思：假设 n = 4。

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

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

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

如果它有任何区别，我不一定关心“按顺序记住最后 n 个唯一数字”。我特别需要知道，添加时从列表中删除了哪些元素（如果有的话）。

Answer 1

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

然后在您描述的步骤中 搜索队列中您更改它的数字，以查看该数字是否在哈希表中，这将是恒定时间而不是使用队列的线性时间。

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

您的步骤如果找到数字，则可以在恒定时间内删除该位置的数字，因为您已经有了要删除的数字的位置。（位置是指您从哈希表中获得的指针）。

更新：

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