我需要一个支持O(1)以下操作的数据结构:
- myList.添加(项目)
- myList.remove(Item.ID) ==> 它实际上需要随机访问
myList.getRandomElement()(等概率)
--(请注意,getRandomElement() 并不意味着随机访问,它只是意味着:“随机给我一个项目,概率相等”)
<
请注意,我的项目是唯一的,所以我不关心是否使用了 List 或 Set。 我检查了一些java数据结构,但似乎没有一个是解决方案:
- HashSet 在 O(1) 中支持 1,2,但它不能在 O(1) 中给我一个随机元素。我需要调用 mySet.iterator().next() 来选择一个随机元素,这需要 O(n)。
- ArrayList 在 O(1) 中执行 1,3,但它需要进行线性搜索才能找到我要删除的元素,尽管它需要 O(n)
有什么建议吗?请告诉我应该调用哪些函数?
如果 java 没有这样的数据结构,我应该使用哪种算法来达到这样的目的?
最佳答案
如果内存允许,您可以使用 HashMap 和 ArrayList 的组合,如下所示:-
- Store numbers in ArrayList arr as they come.
- Use HashMap to give mapping arr[i] => i
- While generating random select random form arrayList
删除:-
- check in HashMap for num => i
- swap(i,arr.size()-1)
- HashMap.remove(num)
- HashMap(arr[i])=> i
- arr.remove(arr.size()-1)
所有操作都是O(1)
但额外的O(N)
空间
关于java - (Java) 快速插入、删除和随机选择的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21622911/