与编程相关的招聘，都会准备很多考题，一不小心考生就在考题上栽了跟头，特别是没有多少工作经验的应届毕业生，往往回答得过于理论化，很难令考官满意。为此，我们特意推出本系列，通过对真实考题的分析让大家在回答考题时有更多的实用性，让考官满意，顺利找到工作。
高效生成随机数组
爪哇米工作室 陈跃峰
算法是程序的灵魂，所以在面试中基本都要考核应聘者的算法能力。算法的种类有很多，每种算法在实现时都有独立的方式，本文将介绍的生成随机数组的算法只是其中的一种。生成随机数组，即固定的一组数组但是数字位置随机的数组，是一种反映应聘者基础数字逻辑掌握程度的基础算法。下面以一个简单的例子来介绍高效生成随机数组的算法实现。
招聘题目：生成20个随机数字，该组数字中包含2组1-10之间的整数，即包含2个1、2个2，依次类推，但是每个数字的位置是随机的。
答案A：
int num[] = new int[20];
int index = 0; //数组下标
int ranNum; //随机数字
int time = 0; //数字已出现次数
Random r = new Random();
while(true){
ranNum = r.nextInt(9) + 1; //随机1-10之间的数字
//统计数字ranNum已出现次数
time = 0;
for(int i = 0;i < index;i++){
if(num[i] == ranNum){
time++;
}
}
//如果未出现2次
if(time != 2){
num[index] = ranNum;
index++; //继续赋值下一个
}
if(index == num.length){ //全部赋值
break;
}
}
答案B：
//生成2组1-10之间的规则数字
int num[] = new int[20];
for(int i = 0;i < num.length;i++){
num[i] = i / 2 + 1;
}
//随机打乱数字顺序
Random r = new Random();
int times = 30; //两两交换次数
int ranIndex; //随机下标
int temp; //交换变量
int cIndex; //当前下标
for(int i = 0;i < times;i++){
ranIndex = r.nextInt(20); //[0-20]之间的随机数，作为下标
//和下标i % 20交换
cIndex = i % 20;
if(cIndex != ranIndex){
temp = num[cIndex];
num[cIndex] = num[ranIndex];
num[ranIndex] = temp;
}
}
正确答案：B
答案分析
在答案A中，使用的是自然思维，既按照随机生成一个1-10之间的数字，然后判断该数字是否已在数组中出现2次，如果未出现2次，则将该数字赋值到数组中，接着随机下一个数字。使用这种方式实现的代码，虽然理论上可以完成要求的功能，但是在程序的执行效率上很不稳定，每次随机的过程需要的时间的耗时差异很大，甚至有可能卡住程序的执行，所以在程序中生成比较多的随机数字组合时，不推荐这样进行实现。
在答案B中，采用的思路是一种变通的思路，即首先生成一组规则的数字，然后随机打乱改组数字的顺序。使用这种思路，程序的执行效率很稳定，而且实现起来比较简单。
实现的具体步骤是，首先生成两组1-10之间的整数，按照1，1，2，2，……这样的顺序依次赋值到数组中，这样得到的是一个规则的数组num，这个数组中包含所有需要的数字，即2组1-10之间的数字，但是数字的顺序是规则的。接着使用两两交换的方式随机交换数组中数字的位置，交换的方法是生成一个0到数组长度(不包含)的随机数字，作为一个数组交换时的下标，然后和数组当前的下标，即第一次下标为0，第二次下标为1，的元素进行交换，这样经过一定次数的交换以后，数组中的数字位置就变得随机了。而每次的交换消耗的时间是基本固定的，所以实现起来整个算法的执行效率很稳定，生成的速度也很高效。
实际应用
高效生成随机数组这种算法在实际的程序开发中也大量的进行使用。例如在棋牌类的游戏开发中，例如斗地主、双扣等，在每次游戏开始时，都需要打乱扑克牌的顺序，然后再将打乱以后的扑克牌依次发放给每个游戏玩家。而这种打乱扑克牌顺序的算法通常就被称作洗牌算法。
从程序开发的角度看洗牌算法，实际上生成的就是一组规则的随机数字，例如对于一副扑克牌来说，在程序中如果需要代表一副扑克牌，根据扑克牌的特点(每幅牌包含54张不同的牌)则只需要为每张牌进行编号即可，例如将扑克牌中的每张牌依次对应编号成0-53之间的整数，那么一副牌就是一个包含0-53之间所有整数的数组。而洗牌就是将这样一个规则的数组变成一个随机数组，但是必须包含所有0-53之间的所有整数，这个要求和前面介绍中的算法实现的功能是一致的。
则根据前面介绍的算法，在一副扑克牌的斗地主游戏中实现洗牌的代码如下：
//生成一幅牌，编号为0-53
int poker[] = new int[54];
for(int i = 0;i < poker.length;i++){
poker[i] = i;
}
//洗牌
Random r = new Random();
int times = 54; //两两交换次数
int ranIndex; //随机下标
int temp; //交换数字
int cIndex; //当前下标
for(int i = 0;i < times;i++){
ranIndex = r.nextInt(54); //[0-53]之间的随机数
//和下标i % 54交换
cIndex = i % 54;
if(cIndex != ranIndex){
temp = poker[cIndex];
poker[cIndex] = poker[ranIndex];
poker[ranIndex] = temp;
}
}
点评：在该代码中，利用前面介绍的算法首先生成一个包含[0,53]之间所有整数的规则数组poker，然后再使用两两交换的方式对于该数组中的元素交换54次，这个次数可以根据需要进行调整，从而得到了一个符合逻辑要求的数组poker。而对于玩家来说，poker这个数组就是一副被洗过的扑克牌，可以以此为基础进行游戏后续的逻辑的开发了。
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/Mailbomb/archive/2010/07/06/5715435.aspx