(Java)数据结构,用于快速检查,删除和随机选择

Question

我需要一个支持O(1)中的以下操作的数据结构:

1. 我的列表.新增项目)
2. 我的列表.remove(Item.ID) ==>它实际上需要随机访问

3. 我的列表.getRandomElement()(概率相等)

   - (请注意,getRandomElement()并不意味着随机访问,它只是意味着:"以相同的概率随机给我一个项目")

请注意我的项目是唯一的,所以我不在乎是否使用List或Set.我检查了一些java数据结构,但似乎没有一个是解决方案:

1. HashSet在O(1)中支持1,2,但它不能在O(1)中给我一个随机元素.我需要调用mySet.iterator().next()来选择一个随机元素,它取O(n).
2. ArrayList在O(1)中执行1,3,但它需要进行线性搜索才能找到我想要删除的元素,尽管需要O(n)

有什么建议？请告诉我应该拨打哪些功能？

如果java没有这样的数据结构,我应该为此目的使用哪种算法？

Answer 1

如果内存允许,您可以使用HashMap和ArrayList的组合,如下所示: -

1. 将数字存储在ArrayList arr中.
2. 使用HashMap给出映射arr [i] => i
3. 同时生成随机选择随机形式的arrayList

删除: -

1. 在HashMap中检查num => i
2. 交换(I,arr.size() - 1)
3. HashMap.remove(NUM)
4. HashMap(arr [i])=> i
5. arr.remove(arr.size() - 1)

所有操作都是O(1)额外的O(N)空间

Answer 2

您可以将HashMap（ID为数组索引）与数组（或ArrayList）结合使用。

add可以通过简单地添加到数组并将ID和索引添加到O（1）中来完成HashMap。

remove可以在O（1）中执行以下操作：从中进行查找（和删除）HashMap以找到索引，然后将数组中的最后一个索引移至该索引，在中更新该元素的索引，HashMap并将数组大小减小一个。

getRandomElement 可以在O（1）中通过从数组返回一个随机元素来完成。

例：

Array: [5,3,2,4]
HashMap: [5->0, 3->1, 2->2, 4->3]

删除3：

Look up (and remove) key 3 in the HashMap (giving 3->1)
Swap 3 and, the last element, 4 in the array
Update 4's index in the HashMap to 1
Decrease the size of the array by 1

Array: [5,4,2]
HashMap: [5->0, 2->2, 4->1]

要添加6：

Simply add it to the array and HashMap

Array: [5,4,2,6]
HashMap: [5->0, 2->2, 4->1, 6->3]