java - 插入、包含、删除和按索引获取元素的时间常数的数据结构

Question

我有一个大数据集 Person在列表中排队的对象。我希望数据结构能够高效地执行以下操作。

1. 添加 Person在队列的末尾。
2. 删除第一个 Person .
3. 查找特定的 Person存在，如果存在，将其移除并放在队列的末尾。
4. 获取特定的 Person根据其位置。

所有这些操作的时间复杂度是 O(1) 吗？ 到目前为止，我想出了两种方法，但它们都不是最优的。

1. ArrayList<Person> + HashMap<Person, Integer>

   HashMap存储 Person 的索引对象。这为操作 2 和 3 提供了 O(n) 时间(删除 ArrayList 中的元素)

2. ArrayDeque<Person>/LinkedList<Person>

   前两个操作的复杂度为 O(1)，后两个操作的复杂度为 O(n)。

在我的例子中，空间复杂度不能大于 O(n)。操作 4 强度较低，因此我可以容忍执行此操作的效率稍低的方法。

如有任何建议，我们将不胜感激。提前致谢!

Answer 1

我假设要求 3 的意思是“通过某个键找到一个人”(例如，它的姓氏)？

我有一种强烈的感觉，您不能在 O(1) 中满足所有这些要求，甚至不能满足摊销时间(这样的事情会众所周知)。但是您可以将所有这些都放在 O(log N) 中。您必须从实现红黑树(C++ 中的 std::map，我相信这是 Java 中的 SortedMap)开始，然后修改节点结构以保留其子树中所有节点的计数。这将为您提供 O(log N) 按索引访问，以及 O(log N) 在树中的任何位置插入和删除。通过(红黑树节点的)外部哈希表可以在 O(1) 中通过某个键找到一个人。

如果您对要求 4 的 O(N) 没问题，那么我建议在 Java 中使用类似 LinkedHashMap 的东西，它在 O(1) 中为您提供要求 1 到 3，而 req. 4 可以通过迭代完成，时间复杂度为 O(N)。