[小技巧]怎样随机的将1到100的数字放入一个数组?

最近挺忙,但是也发现了一些有意思的东西。直接入正题吧。

有些算法的经典案例就是TSP旅行商问题。而旅行商问题就一定有城市,而城市的线路有很多条。在初始化解的时候,我们很自然的想把城市编号打乱放进一个一维数组里作为一条解的内容。

但可行吗?以Java为例,Java的Random类对象有一个方法叫nextInt(),参数可以为一个int型整数,意味着你可以取得 0~这个整数-1 的随机整数。

假设我们有100个城市,也就是0~99这100个数字,如何随机放进一个有100个数组单元的数组呢?

思路1:

遍历这个数组,对每一个元素随机生成一个0~99之间的某个数字,也就是nextInt(100)。然后每一次取的时候在循环内再放一个查找重复元素的循环,判断这个数字到底有没有出现过,如果出现过就重新取。

评价:这个思路从我脑袋蹦出来的时候就被我否决了。因为实在太耗时间了。当数字到90多的时候,随机生成的数字符合要求的真的会很少,到最后可能会不停地循环。

思路2:(来源:http://wsjiang.iteye.com/blog/1775341

评价:这个东西我试过,但效果很不好,乱序效果很一般。

思路3:

其实我们打牌的时候,也就是将牌的顺序打乱的过程。当一副新的扑克牌拿到手中的时候,我们要做的就是洗牌。所以事实上,随机也就等于打乱的结果。所以做法就是先将数字全部存入数组中,然后调用shuffle函数直接打乱,得到的就已经满足随机插入数组的要求了。

但Java里的shuffle是Collections类的东西,必须用List才可以调用,而List不接受基本数据类型,而接受它们的包装类。如果我们用习惯了int,double等基本数据类型,也差不多要开始学一学他们的包装类了。(由于博主实际使用的时候要用浮点型double操作,所以以下代码是针对double的。double的包装类就是Double,而int的包装类是Integer。)比较麻烦的是,包装类对象虽然能用一些方法,但要转成基本数据类型,还是需要遍历一个一个装。

最后的结果让我十分满意。但这就不是“随机插入100个数字”了。

其实由于随机的值不为人所控制,所以,也许不重复的插入数字本来就很耗时间吧。从另一个角度来说,打乱的方法也更贴合现实。