写在前面
前天去面试了，给出的笔试中有这样的一道算法题，产生一个int数组，长度为100，并向其中随机插入1-100，并且不能重复
当时，脑子一热，也没想那么多，就用集合实现了一下，经面试官提醒，发现还有更好的方式来实现。
代码
首先看一下这样一段代码
1 namespace Wolfy.RandomDemo 2 { 3 class Program 4 { 5 static void Main(string[] args) 6 { 7 List<int> lst = new List<int>(); 8 Random r = new Random(); 9 while (true) 10 { 11 int temp = r.Next(1, 101); 12 if (lst.Count == 100) 13 { 14 break; 15 } 16 if (!lst.Contains(temp)) 17 { 18 lst.Add(temp); 19 } 20 } 21 for (int i = 0; i < lst.Count; i++) 22 { 23 Console.WriteLine(lst[i]); 24 } 25 Console.Read(); 26 } 27 } 28 }
虽然上面的代码，实现题目的要求，但是如果是1到100万或者更大，这样的每次判断是否包含这样的一个数，势必会影响到性能。
网上找到一种更好的实现方式：
(1)把N个数放到容器A(int数组)中.
(2)从N个数中随机取出1个数放入容器B(int数组)中.
(3)把容器A中最后一个数与随机抽取的数对调 或者 把容器A中最后一个数覆盖随机抽取出来的数.
(4)这时从容器A(假设N个数,索引0 到 索引N-2)之间随机取一个数.再放入容器B中,重复此步骤.
说明:也就是第二次是从容器A中 第一个元素到倒数第二个元素 中随机取一个数.
这种好处是,随机数所取范围逐步缩小,而且杜绝了大数据时集合执行删除操作时产生的瓶颈.
代码实现
1 namespace Wolfy.RandomDemo 2 { 3 class Program 4 { 5 static void Main(string[] args) 6 { 7 int[] result = GetRandom(100); 8 for (int i = 0; i < result.Length; i++) 9 { 10 Console.WriteLine(result[i]); 11 } 12 Console.WriteLine("over:" + result.Length); 13 Console.Read(); 14 } 15 /// <summary> 16 /// 获得无重复随机数组 17 /// </summary> 18 /// <param name="n">上限n</param> 19 /// <returns>返回随机数组</returns> 20 static int[] GetRandom(int n) 21 { 22 //容器A和B 23 int[] arryA = new int[n]; 24 int[] arryB = new int[n]; 25 //填充容器a 26 for (int i = 0; i < arryA.Length; i++) 27 { 28 arryA[i] = i + 1; 29 } 30 //随机对象 31 Random r = new Random(); 32 //最后一个元素的索引 如n=100，end=99 33 int end = n - 1; 34 for (int i = 0; i < n; i++) 35 { 36 //生成随机数 因为随机的是索引 所以从0到100取，end=100 37 //一个大于等于 minValue 且小于 maxValue 的 32 位带符号整数，即：返回的值范围包括 minValue 但不包括 maxValue。 38 //如果 minValue 等于 maxValue，则返回 minValue 39 // 40 int minValue = 0; 41 int maxValue = end + 1; 42 int ranIndex = r.Next(minValue, maxValue); 43 //把随机数放在容器B中 44 arryB[i] = arryA[ranIndex]; 45 //用最后一个元素覆盖取出的元素 46 arryA[ranIndex] = arryA[end]; 47 //缩减随机数生成的范围 48 end--; 49 } 50 //返回生成的随机数组 51 return arryB; 52 } 53 } 54 }
总结
实现方式有很多种，但是如果能用高效的方式就用高效的方式实现。这种生成无重复的随机数，可以在运用在抽奖系统中。
| 博客地址： | http://www.cnblogs.com/wolf-sun/ |
| 博客版权： | 本文以学习、研究和分享为主，欢迎转载，但必须在文章页面明显位置给出原文连接。 如果文中有不妥或者错误的地方还望高手的你指出，以免误人子弟。如果觉得本文对你有所帮助不如【推荐】一下！如果你有更好的建议，不如留言一起讨论，共同进步！ 再次感谢您耐心的读完本篇文章。http://www.cnblogs.com/wolf-sun/p/4321609.html |
