高效的数据结构用于快速随机访问、搜索、插入和删除。

Question

高效的数据结构用于快速随机访问、搜索、插入和删除。

arraysdata-structureslistlinked-list

18

我正在寻找一种数据结构(或多种数据结构)，它可以让我维护一个整数有序列表，没有重复值，且索引和值在相同的范围内。

我需要四个主要操作具有高效性，大概按照重要性顺序排序：

从给定索引获取值
查找给定值的索引
在给定索引处插入值
删除给定索引处的值

使用数组，1的时间复杂度是O(1)，但2是O(N)，而且插入和删除都很昂贵（我认为也是 O(N)）。

链表的插入和删除时间复杂度是O(1)（一旦你有了节点），但1和2是O(N)，因此抵消了收益。

我尝试保持两个数组a[index]=value和b[value]=index，这样就能使得1和2的时间复杂度变成O(1)，但3和4的操作变得更加代价高昂。

是否有更适合此需求的数据结构？

- Leonel

2

不应该影响，但这是C++。 - Leonel

1

这非常重要；并不是所有的编程语言都提供相同的数据结构。例如，这个特定问题可以通过 C Judy 数组或 C# CPTrie 很有效地解决。(当然，像 Ayman 建议的那样，也可以使用某种平衡二叉树。) - Qwertie

这个问题实际上没有意义：如果你有一个有序的整数列表，那么在给定的索引位置插入一个值是什么意思呢？如果它是有序的，那么只有一个位置可以合理地插入。同样地，如果没有重复的值，那么你也不能删除特定索引位置的值，因为只有一个索引位置可以找到该值。 - Maks Verver

这个问题其实没有什么意义：如果你有一个有序的整数列表，那么在给定的索引位置插入一个值是什么意思呢？如果它是有序的，那么逻辑上只有一个位置可以插入。同样地，如果没有重复值，那么你也不能在特定的索引位置删除一个值，因为只有一个索引位置可以有这个值。 - undefined

8个回答

4

如何使用带有二进制搜索的排序数组呢？

插入和删除速度较慢，但是如果数据是纯整数并且使用C或C ++，可以通过调用memcpy()进行优化。如果您知道数组的最大大小，则甚至可以在使用数组期间避免任何内存分配，因为您可以将其预先分配到最大大小。

“最佳”方法取决于您需要存储多少项以及与查找相比，您需要多频繁地插入/删除。如果您很少插入或删除，则具有对值的O(1)访问的排序数组肯定更好，但是如果您经常插入和删除事物，则二叉树可能比数组更好。对于足够小的n，数组在任何情况下都很可能击败树。

如果存储大小是问题，那么数组比树更好。树还需要为存储的每个项目分配内存，并且内存分配的开销可能非常大，因为您只存储小值（整数）。

您可能需要测试哪个更快，如果您从排序数组中插入/删除整数，则是复制整数还是具有它的内存（de）分配的树。

- lothar

插入和删除是OP清单上的最后一项，由于它们是整数，可以通过调用memcpy()进行优化。 - lothar

“ordered” 部分很重要，所以我不能对数据进行排序。 - Leonel

1

@Leonel ordered 意味着根据您指定的排序规则进行排序。 - lothar

可能他的意思是“插入顺序”。 - Hengameh

1

如何使用红黑树实现查找第二个元素？我们可以在每次插入/删除操作时让它们计算其子节点数。这不会显著延长这些操作的时间。然后，在对树进行遍历以查找第i个元素时，可以在log n时间内完成。但是我没有看到Java或STL中实现此方法的代码。

- Jarek Czekalski

1

我非常喜欢平衡二叉树。它们有时比哈希表或其他数据结构慢，但更加可预测；对于所有操作，它们通常是O(log n)的时间复杂度。我建议使用红黑树或AVL树。

- Zifre

哈希表不会保持数据有序。 - Greg Rogers

哎呀，我没看到有序的部分……不过我已经修复了。 - Zifre

1

我不知道你使用的是什么语言，但如果是Java，你可以利用LinkedHashMap或类似的集合。它具有列表和映射的所有优点，大多数操作提供常数时间，并且具有大象一样的内存占用。 :)

如果你没有使用Java，那么LinkedHashMap的想法可能仍然适合你的问题的可用数据结构。

- Rob Hruska

1

你如何使用LinkedHashMap获取随机元素？ - Hengameh

1

使用向量来访问数组。

使用映射作为搜索索引，以下标方式进入向量。

给定下标，从向量中获取值 O(1)
给定键，使用映射查找 值的下标。O(lnN)
插入值，在向量上推回 O(1) 摊销，在映射中插入下标 O(lnN)
删除值，从映射中删除 O(lnN)

- EvilTeach

这对于任意索引的插入和删除无效。 - Maks Verver

这对于任意索引的插入和删除是不起作用的。 - undefined

0

如何使用Treemap？所描述的操作的时间复杂度为log(n)。

- CookieOfFortune

Java TreeMap（假设这是您的意思）不支持通过索引进行查询、插入或删除操作。 - Maks Verver

Java TreeMap（假设这是你的意思）不支持按索引查询、插入或删除。 - undefined

0

如果你正在使用.NET，那么根据微软文档 http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

SortedDictionary和SortedList都具有O(log n)的检索时间复杂度
SortedDictionary具有O(log n)的插入和删除操作时间复杂度，而SortedList具有O(n)。

这两者的区别在于内存使用和插入/删除速度。SortedList使用的内存比SortedDictionary少。如果SortedList一次性从排序数据中填充，则比SortedDictionary更快。因此，根据情况选择最适合您的方法。

此外，关于链表的论点并不完全正确，因为虽然插入可能是O(1)，但必须遍历列表以找到插入点，因此实际上并不是。

- BenAlabaster

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ayman Hourieh · Accepted Answer

我会使用红黑树将键映射到值。这可以让你在 1、3、4 操作时的复杂度为 O(log(n))。同时，它还能保持键的排序。

对于 2 操作，我会使用哈希表将值映射到键，这可以带来 O(1) 的性能。同时，添加和删除红黑树中的键时，需要维护哈希表的更新，这会增加 O(1) 的开销。