我在选择正确的数据结构时遇到问题，这些是要求:
- 我必须能够插入和删除元素
- 我还必须能够获取集合中元素的索引(集合中的顺序)
- 元素有一个唯一的标识符号
- 我可以使用任何标准对元素进行排序(如有必要)
排序并不是必须的，重要的是获取元素的索引，无论内部如何实现，但无论如何我认为最好的方法是排序。 元素的索引是集合内的顺序。所以必须使用某种顺序。当我删除一个元素时，从该元素到最后的其他元素会更改它们的顺序/索引。
第一种方法是使用链表，但我不需要 O(n)。 我也考虑过使用和排序的字典，这会给 O(log n) 查找/插入/删除，不是吗？ 有更好的方法吗？我知道 TRIE 会为常见操作提供 O(1)，但我不知道如何获取元素的索引，我将不得不遍历 trie 并给出 O(n)，我错了吗？
最佳答案
听起来你想要一个有序的数据结构，即(平衡的)BST。插入和删除确实是 O(lg n)，这足以满足许多应用程序。如果您还希望元素在结构中有一个索引，那么您需要一个order statistic tree。 (例如，参见 CLR，算法简介，第 14 章)它在 O(lg n) 中提供了此操作。动态重新排序整个集合的时间复杂度为 O(n lg n)。
如果您所说的“集合中的顺序”是指任何随机顺序都足够好，那么只需使用动态数组(向量):分摊 O(1) 追加和删除，O(n lg n) 就地排序，但是 O(n) 查找直到你进行排序，之后查找变为 O(lg n)二进制搜索。不过，如果数据要保持排序，则删除操作的时间复杂度为 O(n)。
如果您的数据是类似字符串的，您可以像扩展 BST 一样扩展一个 trie 以成为订单统计树。
关于algorithm - 在集合中查找元素的索引，使用哪个集合？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7639873/