用于删除随机元素的标准Java类

问题描述

我想找到一个有效支持以下接口的类：

• 添加元素
• 删除元素，给定其键
• 删除随机元素

“有效地”是指O（1）或恒定时间。

实现此目的的一种方法是让一个类包含一个数组和一个哈希映射。

• 添加元素：将其添加到两个元素中，并将其在数组中的位置保留在元素中
• 按键删除元素：从哈希图中删除，然后使用保存的位置将其从数组中删除
• 删除随机元素：在数组中选择一个随机单元格，然后删除该单元格中的元素。使用密钥将其从哈希中删除。

每当我们从数组中删除元素时，只需将其替换为最后一个元素并更新数组大小即可。

我可以写这类的类，但是我想知道这样的类是否已经可用。

思路：

您可以在恒定时间内从ArrayList中删除随机元素，只要您实际上并不关心列表中事物的顺序：

 E removeRandomItem(List extends E> list) {
  int e = aRandom.nextInt(list.size());
  Collections.swap(list, e, list.size() - 1);
  return list.remove(list.size() - 1);
}