不重复随机数列生成算法

《不重复随机数列生成算法》由会员分享，可在线阅读，更多相关《不重复随机数列生成算法（4页珍藏版）》请在装配图网上搜索。

1、不重复随机数列生成算法本文将讲述一个高效的不重复随机数列的生成算法，其效率比通常用 hashtable 消重的方法要快很多。作者：eaglet转载请注明出处。首先我们来看命题：给定一个正整数n需要输出一个长度为n的数组，数组元素是随机数，范围为 0 - n-1，且元素不能重复。比如n = 3时，需要获取一个长度为3的数组， 元素范围为0-2，比如 0,2,1 。这个问题的通常解决方案就是设计一个 hashtable ，然后循环获取随机数，再 到hash table中找，如果hash table中没有这个数，则输出。下面给出这种算 法的代码public static int GetRandomS

2、equenceO(int total)int hashtable = new inttotal;int output 二 new inttotal;Random random = new Random。；for (int i 二 0; i 0)num = random.Nex t(0, tot al);outputi二 num;hashtablenum = 1;return output;代码很简单，从0到total - 1循环获取随机数，再去hash table中尝试匹 配，如果这个数在 hashtable 中不存在，则输出，并把这个数在 hashtable 中 置1，否则循环尝试获取随机数

3、，直到找到一个不在 hashtable 中的数为止。这 个算法的问题在于需要不断尝试获取随机数，在 hashtable 接近满时，这个尝 试失败的概率会越来越高。那么有没有什么算法，不需要这样反复尝试吗？答案是肯定的。如上图所示，我们设计一个顺序的数组，假设 n = 4第一轮，我们取0 - 3之间的随机数，假设为2,这时，我们把数组位置为2 的数取出来输出，并把这个数从数组中删除，这时这个数组变成了第二轮，我们再取 0-2 之间的随机数，假设为 1，并把这个位置的数输出，同 时把这个数从数组删除，以此类推，直到这个数组的长度为 0。这时我们就可以 得到一个随机的不重复的序列。这个算法的好处是不

4、需要用一个 hashtable 来存储已获取的数字，不需要反复 尝试。算法代码如下：public static int GetRandomSequencel(int total) List input 二 new List(); for (int i 二 0; i total; i+) inp ut .Add(i);List output 二 new List();Random random = new Random();int end = total; for (int i 二 0; i / public static int GetRandomSequence2(int total)int

5、 sequence = new inttotal;int output 二 new inttotal;for (int i 二 0; i total; i+)sequencei = i;Random random = new Random();int end = total 1;for (int i 二 0; i total; i+)int num = random.Nex t(0, end + 1);outputi二 sequencenum; sequencenum = sequenceend;end;return output;下面是n等于1万，10万和100万时的测试数据，时间单位为毫秒。从测试数 据看GetRandomSequence2的用时和n基本成正比，线性增长的，这个和理论上 的算法复杂度O(n)也是一致的，另外两个算法则随着n的增大，用时超过了线 性增长。在1 百万时，我的算法比用 hashtable 的算法要快10 倍以上。100001000001000000GetRandomSequence05441075GetRandomSequencel111038124205GetRandomSequence21782