允许通过索引访问元素并在O（1）中删除它们的数据结构 [英] Data structure that allows accessing elements by index and delete them in O(1)

问题描述

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

I have following task (as part of bigger task):

我需要使用 k 元素从数组之类的数据结构中删除它（k是任何可能的索引）。数组具有O（n）用于删除元素，列表具有O（n）用于搜索元素。我想在O（1）时间内同时执行这两项操作。

I need to take an k element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would like to do both operations in O(1) time.

我应使用哪个数据结构满足此要求？

Which data structure should I use to meet this requirement?

说明：

删除索引（5）上的元素会将元素从索引（6）移至索引（5）。

Deleting element on index(5) will move element from index(6) to index(5).

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

This particular task is topcoder srm 300 div2 500 points problem. It does not require such sophisticated data structure (simple java methods will do the job since max data is really small), but I am curious how to deal with much bigger problem using c-like thinking about data.

因此，对于这个问题，我可能坚持不懈了？但是我将对其进行分析并在以后下班后编辑问题（如果您真的很好奇，您可以在顶级编码器上看到任务）。

So maybe I am sticked to much to array for this problem? But I will analyze it and edit question later, after work (if you are really curious, you can see task on top coder).

推荐答案

我相信您的要求是不可能的。

I believe what you're asking for is impossible.

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

However, if you can relax your requirement for indexing to O(log n), then ropes may be able to satisfy it, although I'm not sure if they have a probabilistic or deterministic guarantee (I think it's probabilistic).

这篇关于允许通过索引访问元素并在O（1）中删除它们的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！