加载中…
个人资料
大山
大山
  • 博客等级:
  • 博客积分:0
  • 博客访问:352
  • 关注人气:17
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

如何快速得到无重复的 1 - 100 数字的乱序序列?

(2008-05-22 22:23:49)
标签:

数组

序列

for

next

个数

洗牌

无重复

交换

算法

随机

快速

it

分类: 瞎捣鼓之大山谈面试

答:传统思路:

    第一个数:随机产生一个 1 - 100 之间的数;

    第二个数:随机产生一个,和第一个比较,如果相同,就再产生一个随机的,直到不同为止;

    第三个数:随机产生一个,和第一、第二个比较,如果相同,就再产生,直到不同为止;

    ......以此类推,绝对不是一个好办法,费时费力费资源,效率低。

    重新分析特点:1 到 100 总共 100 个数,无重复全部输出;

    新思路出现了:先把 1 到 100 顺序存放在一个长度为 100 的数组中,然后随机产生两个 1 到 100 的数字,假设 a = 4 , b = 21 ,然后把处于数组 [第 4 位] 和 [第 21 位] 的数字对调。同样方法,进行 N 次,序列里的数字就变成了乱序,而且,因为是对调,所以也就不会出现重复问题。

代码:

    int[] arr = new int[100]; //初始化数组

    for(int i=1;i<=100;i++)

    {

        arr[i] = i;           //给每个单元顺序赋值

    }

    Random rnd = new Random();//初始化随机数生成器

    int N = 200;              //假设重复对调 200 次

    for(int i=0;i<N;i++)

    {

        int a = rnd.Next(0,100);//随机选取两个单元下标

        int b = rnd.Next(0,100);//区间范围 0 ~ 99

 

        int temp = arr[a];     //经典的两数交换

        arr[a] = arr[b];

        arr[b] = temp;

    }

    //现在得到的数组就是乱序无重复数组

    其实,这个思路就相当于:在一个袋子里,扔进去编号为 1-100 的 100 个球,然后摇晃袋子,相当于两个球在交换位置,得到的自然也就是乱序的,球不会变,所以是无重复的。

    应用:扑克牌游戏的洗牌程序,共有 52 张扑克,洗 N 次,得到随机无重复结果。

 

 

 

 

 

 

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有