如何确保不重复随机生成的数字？

Question

可能重复:
O(1)中的唯一(非重复)随机数？
如何有效地生成0和上限N之间的K个非重复整数列表

我想在某个diapason中生成随机数,我必须确定,每个新数字都不是前者的副本.一种解决方案是将以前生成的数字存储在容器中,并且每个新数字都检查容器.如果容器中有这样的数字,那么我们生成agin,否则我们使用并将其添加到容器中.但是对于每个新的数字,这个操作变得越来越慢.有没有更好的方法,或任何可以更快地工作并确保代的唯一性的兰特函数？

编辑:是的,有一个限制(例如从0到1.000.000.000).但我想生成100.000个唯一数字!(如果解决方案是使用Qt功能,将会很棒.)

Answer 1

随机数是否有范围？如果您对随机数有限制并且继续生成唯一的随机数,那么您将以随机顺序得到x..y中所有数字的列表,其中xy是随机数的有效范围.如果是这种情况,您可以通过简单地生成所有数字的列表x..y并对其进行混洗来大大提高速度,而不是生成数字.

Answer 2

我认为有3种可能的方法,取决于范围大小,以及您可以使用其他算法所需的性能模式.

1. 创建一个随机数,看它是否在(一个已排序的)列表中.如果没有添加和返回,否则尝试另一个.
   • 您的列表将增长并消耗您需要的每个数字的内存.如果每个数字都是32位,则每次至少增加32位.
   • 每个新的随机数都会增加命中率,这会使速度变慢.
   • O(n ^ 2) - 我想
2. 为范围中的每个数字创建一个位数组.标记为1/True如果已经返回.
   • 现在每个数字只需1位,如果范围很大,这仍然是一个问题,但现在每个数字只分配1位.
   • 每个新的随机数都会增加命中率,这会使速度变慢.
   • 为O(n*2)
3. 预先填充包含所有数字的列表,将其随机播放,然后返回第N个数字.
   • 列表不会增长,返回的数字不会变慢,
   • 但生成列表可能需要很长时间,并且需要大量内存.
   • O(1)

根据所需的速度,您可以将所有列表存储在数据库中.除了速度之外,它们不需要在内存中.

Answer 3

填写一个包含您需要的号码的列表,然后随机播放列表并从一端选择您的号码.