在固定时间内生成一个唯一的随机数
问题描述：
有没有什么办法在常量时间内生成一个唯一的随机数？我目前正在使用一个包含我所有可能的数字的arrayList。它实现了Collection，我在这个arrayList上调用shuffle方法。我再从ArrayList中移除第0个元素，以获得独特的随机数，但我相信这不可能是固定的时间有2个原因：在固定时间内生成一个唯一的随机数
- remove方法是O（n）
- Collection.shuffle是O（n）
对此有何建议？谢谢！
答
Collection.shuffle确实是O（n），但它只需要调用一次。如果你得到n个随机数，那么这个时间就会扩散到其余的操作中。 （这是摊销分析背后的一种想法，对于你的问题来说这似乎是必要的：或者你需要“分期确定性固定时间”或者“期望固定时间”，就像你可能会用字典那样）
remove方法一般是O（n），但是如果你反复删除最后一个元素而不是第一个元素，数组不需要不断地将元素向下移动，所以它实际上是O（1） - 它只是它的O（n ）在平均和最坏的情况下。
你的问题是不明确的。你想从集合中选择一个单一的值，还是你真的想要一个大小为k的子集而不用替换？如果一个子集，k或其他停止标准是否有固定值？另外，知道你在工作的语言并不会受到伤害。 – pjs 2013-04-23 19:16:53