collections - 在恒定时间内生成唯一的随机数

Question

有没有办法在恒定时间内生成唯一的随机数？我目前正在使用一个包含我所有可能的数字的数组列表。它实现了 Collection，我在这个 arrayList 上调用了 shuffle 方法。然后我从 arrayList 中删除第 0 个元素以获得唯一的随机数，但我相信这不能是恒定的时间，原因有两个：

• 删除方法是 O(n)
• Collection.shuffle 是 O(n)

建议？谢谢！

Answer 1

Collection.shuffle 确实是 O(n)，但只需要调用一次。如果您得到 n 个随机数，则该时间会扩散到其余操作中。（这是摊销分析背后的一种想法，这对于您的问题似乎是必要的：要么你想要“摊销确定性常数时间”，要么“预期常数时间”，就像人们可能对字典所做的那样）

remove 方法一般是 O(n)，但是如果你反复删除最后一个元素而不是第一个元素，则数组不必不断地向下移动它的元素，所以它实际上是 O(1)——它只是它O(n) 在平均和最坏情况下。