重要说明:本博已迁移到 石佳劼的博客,有疑问请到 文章新地址 留言!!!
最近网上看到一道题,如何取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中取一个随机数,作为数组下标,即可在剩下的数字中取随机数了,以此类推。
欢迎来到 石佳劼的博客,如有疑问,请在「原文」评论区 留言,我会尽量为您解答。