算法：如何高效产生m个n范围内的不重复随机数（m<=n)

浏览数：36 / 时间：2015年06月08日

最近网上看到一道题，如何取100以内不重复的100个随机数？代码如下：

var nums = new int[100];
var list = new List<int>();
var random = new Random();
for (int i = 0; i < 100; i++)
{
    int r;
    while (list.Contains(r = random.Next(0, 99))) { }
    list.Add(r);
    nums[i] = r;
}

个人感觉题目很经典，因为实际生活中会经常遇到该类问题，但答案却如此低效，不免有一些失望，打开vs试了一把，果然2分钟都没跑完。

好的题目却没有好的答案些不甘心，便继续探索了一下，发现该问题确实不简单，在《 Programming Pearls 》一书中也有提到，题目为“如何高效产生m个n范围内的不重复随机数（m<=n)”，如果还继续使用以上算法，把m、n放大到10000，估计程序1个小时都跑不完，效率令人发指。

那么该书中是如何解决该问题的呢？代码如下：

var nums = new int[100];
var random = new Random();
for (int i = 0; i < 100; i++)
{
    nums[i] = i;
}
for (int i = 0; i < 100; i++)
{
    var r = random.Next(i, 99);
    Swap(ref nums[i], ref nums[r]);
}

该算法非常巧妙的取随机数的位置（数组的下标），替代取随机数本身，每次取到一个随机数之后，就将其在取值范围中排除，下一次仅会在剩下的数字中取，一次遍历就可以完成随机数的选取，效率相当高。

下面详细讲解该方法：

首先，为数组的每个数字按其位置（数组的下标）赋值，我们获得一个100个数字、顺序排列的数组。
然后，开始取 i-99 范内的随机数，把每次取到的随机数作为位置（数组的下标）与位置（数组的下标）为 i 的数交换数值。这样做的意义是，将已经取到的随机数在取值范围中排除，下一次去随机数仅会在剩下的数字中取。

第2步不太容易理解，我带大家分析每一步的具体原理，你马上就能一目了然：
循环：i = 0 ， r = 39（假设随机数为该值），交换 nums[0] 和 nums[39] 的值。
分析：第一次取到的随机数是39，把位置39的数与位置0的数交换之后，再从位置1开始看该数组，你会惊奇的发现，剩下的是0-99除39以外的所有数字，但它们的位置是1-99，接下来我们仅需要从1-99中取一个随机数，作为数组下标，即可在剩下的数字中取随机数了，以此类推。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

算法：如何高效产生m个n范围内的不重复随机数（m<=n)