这是受到求职面试中的一个问题的启发：如何有效地生成N个唯一的随机数？他们的安全性和分布/偏见无关紧要。
我提出了一种天真的方法，调用 rand（） N 次并通过反复试验消除欺骗，从而得到低效和有缺陷的解决方案。然后我读了这个SO问题，这些算法非常适合获得高质量的唯一数字，它们是O（N）。
但我怀疑有一些方法可以在小于 O（N） 的时间复杂度内为虚拟任务获得低质量的唯一随机数。我有一些可能的想法：
- 存储许多预先计算的列表，每个列表包含 N 个数字，并随机检索一个列表。固定 N 的复杂度为 O（1），使用的存储空间为 O（NR），其中 R 是列表数。
- 生成 N/2 个唯一的随机数，然后将它们除以 2 个不相等的部分（基数为 floor/ceil，偶数为 n+1/n-1）。我知道这是有缺陷的（可以弹出重复项），并且 O（N/2） 仍然是 O（N）。这更像是一种深思。
- 生成一个大的随机数，然后通过一些固定的操作（如按位运算、因式分解、递归、MapReduce 或其他操作）从中挤出更多变体。
- 以某种方式使用准随机序列（不是数学家，只是用谷歌搜索了这个术语）。
你的想法？
大概这个例程有某种输出（即结果被写入某种数组）。 填充大小为 N 的数组（或其他一些数据结构）至少是一个 O（N） 操作，因此您不能比 O（N） 做得更好。
因此，您可以生成一个随机数，如果结果数组包含它，只需将已生成数字的最大数量添加到其中。
检测已经生成的数字是否为 O（1）（使用哈希集）。所以它是 O（n），只有 N 个random()调用。
当然，这是一个假设，我们不会溢出上限（即 BigInteger）。