java中的无替换选择

Question

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

• 可以使用 n 个对象的数组进行初始化，时间复杂度为 O(n)。
• 可以在 O(1) 时间内获得一个随机元素，经过此操作后，所选取的元素 元素从结构中移除。 （无需更换）
• 可以在 O(p) 时间内撤消 p 次“拾取而不替换”操作
• 可以在 O(log(n)) 中从结构中删除特定对象（例如通过 id）
• 可以获取当前结构中的对象数组 O(n)。

其他操作（例如插入）的复杂性（甚至可能性）并不重要。除了复杂性之外，它对于少量的 n 也应该是有效的。

谁能给我实施这种结构的指导方针？我目前实现了一个具有所有上述属性的结构，除了元素的拾取需要 O(d) ，其中 d 是过去拾取的数量（因为我明确检查它是否“尚未拾取”）。我可以找出允许在 O(1) 中进行选取的结构，但这些结构至少在其他操作之一上具有更高的复杂性。

顺便提一句： 请注意，上面的 O(1) 意味着复杂性与 #earlier 选取的元素无关，并且与 #elements 总数无关。

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

Answer 1

HashMap 的插入和删除复杂度均为 O(1)。
你指定了很多操作，但所有这些操作都只不过是插入、删除和遍历：

可以在 O(n) 内使用 n 个对象的数组进行初始化。

n * O(1) 插入。 HashMap 没问题

可以获得一个随机元素
O(1)，经过此操作后，选取的
元素从结构中移除。
（无需更换）

这是唯一需要 O(n) 的操作。

无需任何操作即可撤消 p 'picking
O(p) 中的替换操作

它是一个插入操作：O(1)。

可以删除特定对象（例如
通过 id）从 O(log(n)) 的结构

。

可以获得一个对象数组
当前处于 O(n) 结构中。

您可以在 O(n) 编辑中遍历 HashMap

：
在 O(n) 中选取随机元素的示例：

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

Answer 2

好的，与 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. 将 array[i] 与 array[数组大小 - 1] 交换 (数组中的最后一个元素）。将数组大小减少 1（因为现在少了一个数字） - O(1)

3. 更新 map 中数组位置 i 中新对象的索引 (map.put(array[i], i)) - O(1)

我为 java 和 cpp 表示法的混合表示歉意，希望这有帮助

Answer 3

这是我对使用 Collections.shuffle() 。 html” rel="nofollow noreferrer">ArrayList：

• ✔ 可以在 O(n) 内使用 n 个对象的数组进行初始化。

  是的，尽管成本是摊销的，除非提前知道n。

• ✔ 可以在 O(1) 内获得一个随机元素，此操作后，所选元素将从结构中删除，无需替换。

  是的，选择打乱数组中的最后一个元素；将数组替换为剩余元素的 subList()。

• ✔ 可以在 O(p) 时间内撤消 p 次“拾取而不替换”操作。

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

• ❍ 可以在 O(log(n)) 中从结构中删除特定对象（例如通过 id）。

  不，它看起来像 O(n)。

• ✔ 可以在 O(n) 内获得当前结构中对象的数组。

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

Answer 4

一个被分为“picked”和“unpicked”的数组（或ArrayList）怎么样？您跟踪边界的位置，并进行拾取，在边界下方生成一个随机索引，然后（因为您不关心顺序）将该索引处的项目与最后一个未拾取的项目交换，并递减边界。要取消拾取，只需增加边界即可。

更新：忘记了 O(log(n)) 删除。不过，如果您将 ID 的 HashMap 保存到索引中，那么并不难，只是有点占用内存。

如果您在网上查找，您会发现各种 IndexedHashSet 实现都或多或少地遵循此原则 - 数组或 ArrayList 加上 HashMap.

（不过，如果存在的话，我很想看到一个更优雅的解决方案。）

更新 2： 嗯...或者实际删除是否再次变为 O(n)，如果您必须这样做重新复制数组或移动它们？