7

我正在寻找一些简单的实现数据结构，可以在最短的时间内满足我的需求（在最坏的情况下）：-

（1）弹出第n个元素（我必须保持元素的相对顺序不变）
（2）访问第n个元素。

我不能使用数组，因为它不能弹出，我不想在删除第 i 个元素后有间隙。我试图通过将第 n 个元素与 next 再次与 next 直到 last 交换来消除差距，但这证明了时间效率低下，尽管数组的 O(1) 是无与伦比的。

我尝试使用 vector 并使用 'erase' 进行弹出窗口和 '.at()' 进行访问，但即使这对于时间效率来说并不便宜，尽管它比 array 更好。

4

4 回答 4

3

您可以尝试的是跳过列表- 它支持您在 O(log(n)) 中请求的操作。另一种选择是分层向量，它更容易实现并且需要 O(sqrt(n))。两种结构都很酷，但可惜不是很受欢迎。

于 2012-10-19T14:47:58.857 回答
3

好吧，我认为在数组上实现的分层向量最适合您的目的。虽然分层向量的概念一开始可能是知道的并且有点难以理解，但是一旦你得到它，它就会打开很多问题，你会得到一个方便的武器来非常有效地处理许多问题的数据结构部分。所以建议你掌握分层向量的实现。

于 2012-11-03T04:59:31.047 回答
2

数组将为您提供O(1)查找但O(n)删除元素。列表将为您提供元素的O(n)查找错误O(1)删除。

二叉搜索树将为您提供删除元素的O(log n)查找。O(1)但它不保留相对顺序。

与列表结合使用的二叉搜索树将为您提供两全其美的效果。将节点插入列表（以保持顺序）和树（快速查找）。删除将O(1)。

struct node {
   node* list_next;
   node* list_prev;
   node* tree_right;
   node* tree_left;

   // node data;
};

请注意，如果使用索引作为排序值将节点插入树中，您最终会得到另一个链表假装是一棵树。但是，一旦构建了树，就可以及时平衡树O(n)，而您只需承担一次。

更新

考虑更多这可能不是您的最佳方法。我习惯于查找数据本身而不是它在集合中的相对位置。这是一种以数据为中心的方法。一旦删除节点，使用索引作为排序值就会中断，因为“更高”的索引需要更改。

于 2012-10-19T14:46:57.533 回答
0

警告：不要认真对待这个答案。

理论上，您可以在 O(1) 中同时完成这两项操作。假设这是您要优化的唯一操作。以下解决方案将需要大量空间（并且会泄漏空间），并且创建数据结构需要很长时间：

使用数组。在数组的每个条目中，指向另一个相同的数组，但删除了该条目。

于 2012-10-19T19:38:12.247 回答