java中无需替换的数据结构选取

Question

我经常*发现自己需要具有以下属性的数据结构：

• can be initialized with an array of n objects in O(n).
• one can obtain a random element in O(1), after this operation the picked element is removed from the structure. (without replacement)
• one can undo p 'picking without replacement' operations in O(p)
• one can remove a specific object (eg by id) from the structure in O(log(n))
• one can obtain an array of the objects currently in the structure in O(n).

其他操作（如插入）的复杂性（甚至可能性）并不重要。除了复杂度外，它还应适用于少量的n

有谁能给我提供实施这种结构的指导方针吗？我目前实现了一个具有上述所有属性的结构，除了元素的拾取采用O（d）和d表示过去拾取的数量（因为我显式地检查它是否为“尚未拾取”）。我可以找出允许在O（1）中拾取的结构，但这些结构在至少一个其他操作中具有更高的复杂性

顺便说一句： 注意，上面的O（1）意味着复杂性独立于#早期选取的元素，并且独立于总的#元素

*在蒙特卡罗算法中（从n个元素的“集合”中迭代选取p个随机元素）

Answer 1

以下是我对在^{}上使用^{}的分析：

• ✔ 可以用O（n）中的n个对象数组初始化

  是的，尽管成本是摊销的，除非事先知道n

• ✔ 可以在O（1）中获得一个随机元素，在此操作之后，拾取的元素将从结构中移除，而无需更换

  是的，选择洗牌数组中的最后一个元素；用剩余元素的subList()替换数组

• ✔ 可以撤消O（p）中的p“不替换拾取”操作

  是的，通过add()将元素附加到此列表的末尾

• ❍ 可以从O（log（n））中的结构中移除特定对象（例如通过id）

  不，它看起来像O（n）

• ✔ 可以在O（n）中获得结构中当前的对象数组

  是的，使用toArray()看起来很合理

Answer 2

HashMap的插入和删除复杂性都是O（1）。 您指定了很多操作，但所有操作都是插入、删除和遍历：

can be initialized with an array of n objects in O(n).

n*O（1）插入。HashMap很好

one can obtain a random element in O(1), after this operation the picked element is removed from the structure. (without replacement)

这是唯一需要O（n）的运算

one can undo p 'picking without replacement' operations in O(p)

这是一个插入操作：O（1）

one can remove a specific object (eg by id) from the structure in O(log(n))

O（1）

one can obtain an array of the objects currently in the structure in O(n).

可以在O（n）中遍历哈希映射

编辑： 在O（n）中拾取随机元素的示例：

HashMap map ....
int randomIntFromZeroToYouHashMapSize = ...
Collection collection = map.values();
Object[] values = collection.toArray();
values[randomIntFromZeroToYouHashMapSize];

Answer 3

好的，答案与0verbose相同，只需一个简单的修复就可以得到O（1）随机查找。创建一个存储相同n个对象的数组。现在，在HashMap中存储这些对。例如，假设您的对象（为简单起见，字符串）是：

{"abc" , "def", "ghi"}

创建一个

List<String> array = ArrayList<String>("abc","def","ghi")

使用以下值创建HashMap映射：

for (int i = 0; i < array.size(); i++) 
{
    map.put(array[i],i);
}

O（1）通过选取数组中的任何索引，可以轻松实现随机查找。唯一出现的复杂情况是删除对象时。为此，请：

1. 在^{中查找对象。获取其数组索引。我们把这个索引称为i（map.get(i)）-O（1）

2. 将数组[i]与数组[size of array-1]（数组中的最后一个元素）交换。将数组的大小减少1（因为现在少了一个）-O（1）

3. 更新map（map.put（array[i]，i））-O（1）

我为java和cpp符号的混合表示歉意，希望这能有所帮助

Answer 4

一个数组（或ArrayList）分为“已拾取”和“未拾取”如何？跟踪边界的位置，然后在边界下生成一个随机索引（因为不关心顺序），将该索引处的项与最后一个未勾选的项交换，并减小边界。要取消拾取，只需增加边界

更新：忘记了O（log（n））删除。不过没那么难，只是内存有点贵，如果你把HashMap个ID保存到索引中

如果你在网上浏览，你会发现各种IndexedHashSet实现或多或少都遵循这个原则——一个数组或ArrayList加一个HashMap

（不过，我希望看到一个更优雅的解决方案，如果有的话。）

更新2:嗯。。。或者，如果必须重新复制阵列或将其四处移动，实际移除是否会再次变为O（n）