Fork me on GitHub

算法———随机生成不重复数

发表于 | 分类于 | | 
1
算法———随机生成不重复数

随机生成不重复数算法：用在指定数列中，随机生成多个不重复数算法

算法应用场景：

1.考试系统中生成不重复随机试题的算法及程序设计

2.一种随机播放列表

3.随机抽样模型（随机不重复抽样算法）

4.接单系统随机分配满足条件的多条匹配路线

5.分布式系统随机分配符合要求处理服务器

算法思路：数组的每个元素都有下标，且下标从0开始，利用每次随机数产生的数作为数组下标，将元素保存为标记，下次循环后随机数下标元素如果等于标记数，退出，进行下次循环。

第一次循环：假设随机数为1，数组下标为1的元素是2，将2存储后将其赋值为-1

第二次循环：假设随机数为1，数组下标为1的元素是-1，退出循环

第三次循环：假设随机数为2，数组下标为2的元素是3，将3存储后将其赋值为-1

第四次循环：假设随机数为（1/2），下标为（1/2）的元素为-1，不进行存储，保证了每次保存的数都不相同…………

代码实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//实例：从1-20之间随机生成10个不重复的数 循环次数：不确定
public class Test1
{
    public static void main(String[] args)
    {
        Random ran = new Random();
        int [] array1={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};//定义数组1
        int [] array2=new int[10];//定义数组2
        int index = 0;
        for(int i=0;i<array1.length;i++)
        {
            while(true)
            {
                index = ran.nextInt(20);//随机生成0-19的数
                if(array1[index]!=-1)	//判断元素是否为-1
                {
                    array2[i]=array1[index];//存储到数组2中
                    array1[index]=-1;		//已存储，另其为-1
                    break;					//结束循环
                }
            }
        }
    }
}

上述代码中有一个问题，就是不确定随机多少次，才能生成10个不重复的数

算法优化

优化思路：如何让它循环10次就生成呢，先让随机数赋值给index，然后将index在数组中的元素存储，将这个下标代表的数和最后一个交换，然后让下标减i，这样把第一次生成的数放在最后，并且将下标减i，下次循环的时候就不会在生成这个数了。 确保了以后每一次循环都不会重复

第一次循环：假设随机数为1，数组下标为1的元素是2，将2和20交换。下次随机数范围1-19

第二次循环：假设随机数为1，数组下标为1的元素是20，将20和19交换。下次随机数范围1-18

第三次循环：假设随机数为2，数组下标为2的元素是3，将3和18交换。下次随机数范围1-17

第三次循环：假设随机数为（1/2），数组下标（1/2）的元素是（19/18），将19和17交换（18和16交换）。下次随机数范围1-16（1-15）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//实例：从1-20之间随机生成10个不重复的数 循环次数：10次
public class Test2
{
    public static void main(String[] args)
    {
        Random ran = new Random();
        int [] array1={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};//定义数组1
        int [] array2=new int[10];		//定义数组2
        int index = -1;					//定义数组下标标记
        for(int i=0;i<10;i++)
        {
        	index=ran.nextInt(20-i);		//将随机数赋值给index
        	array2[i]=array1[index];	//存储
        	int temp = array1[index];	//利用中间量交换
        	array1[index] = array1[array1.length-1-i];
        	array1[array1.length-1-i] = temp;
        }
    }

}