6

我有以下任务（作为更大任务的一部分）：

我需要k从像数据结构这样的数组中取出一个元素并将其删除（k 是任何可能的索引）。数组有 O(n) 用于删除元素，而 List 有 O(n) 用于搜索元素。我想在 O(1) 时间内完成这两项操作。

我应该使用哪种数据结构来满足这个要求？

澄清：

删除 index(5) 上的元素会将元素从 index(6) 移动到 index(5)。

这个特殊的任务是 topcoder srm 300 div2 500 points 问题。它不需要如此复杂的数据结构（简单的 java 方法就可以完成这项工作，因为最大数据非常小），但我很好奇如何使用类似 c 的数据思考来处理更大的问题。

所以也许我对这个问题坚持很多？但我会在下班后分析它并编辑问题（如果你真的很好奇，你可以在顶级编码器上看到任务）。

4

4 回答 4

8

我相信你所要求的是不可能的。

但是，如果您可以放宽索引到 O(log n) 的要求，那么绳索可能能够满足它，尽管我不确定它们是否具有概率或确定性保证（我认为它是概率性的）。

于 2013-08-05T07:55:01.423 回答
1

鉴于给定的“约会”问题的性质，它涉及不断选择和删除集合中的“最佳”成员——一个经典的优先级队列。事实上，您需要构建其中两个（男性和女性）。您要么必须在 O(NlogN) 时间（排序列表）中构建它们以进行恒定的 O(1) 移除，要么在线性时间（堆）中构建它们以用于 O(logN) 移除。总的来说，无论哪种方式，您都会得到 O(NlogN)，因为您将删除一个队列的所有内容和另一个队列的大部分内容。

那么问题是什么结构支持任务的另一部分，从圈子中选择“选择者”并删除他和他的选择。由于这也必须执行 N 次，因此任何在 O(logN) 时间内完成删除的方法都不会增加算法的整体复杂性。鉴于重新索引要求，您无法通过快速删除获得 O(1) 索引访问。但实际上，您可以使用树（类似于前面提到的绳索）获得索引访问和删除的 O(logN)。总体而言，这将为您提供 O(NlogN) ，这是您可以做的最好的事情。

于 2013-08-05T09:49:28.453 回答
1

有一个解决方案，在某些情况下可能会令人满意。您必须使用数组和向量来保存删除。每次删除元素时，都会将其索引放入向量中。每次读取某个索引的元素时，都会根据之前的删除重新计算其索引。

说，你有一个数组：

A = [3, 7, 6, 4, 3]

您删除第三个元素：

A = [3, 7, 6, 4, 3] (no actual deletion)
d = [3]

然后阅读 4-th：

i = 4
3 < 4 => i += 1
A[i] = 3

这不完全是 O(1)，但它不依赖于数组长度。仅在一些已删除的元素上。

于 2013-08-05T11:01:28.870 回答
0

唯一在添加和删除元素时开销很小的数据结构是哈希表。唯一的开销是散列函数的成本（如果您采用纯粹的理论方法，它被认为是 O(1)）。

但是，如果您希望它非常高效，您将需要：

  • 大致了解您必须在数据结构中获取的元素数量（并在开始时为所有元素分配一次）。
  • 考虑到密钥的分布方式，选择一个避免冲突的哈希函数（冲突只会破坏哈希表的效率）。

如果你设法把一切都做好，那么你应该是最佳的。

于 2013-08-05T09:14:01.337 回答