算法--生成m个指定范围的不重复随机数的三种方法分析（Java实现）

拼搏现实的明天。 2022-06-14 07:55 102阅读 0赞

# **Q题目** #

如何产生m个在0-N范围内的无重复的随机数(不包含N)

--------------------

# **A解法** #

## **2.1 常见解法有两种：** ##

1.间接获取--采用随机下标从已实例化的数组中取元素
    2.直接获取随机数--然后一一排除

## **2.2 间接法逻辑分析** ##

*  第一步：将指定范围内的所有数循环放入数组arr中
 *  第二步：使用随机下标从该数组中取值，去过的值，赋值为-1
 *  第三步：每次取值时，根据取出来的值是否是 -1来判断该值是否已经取过
 *  第四步：取过，则重新取值，没取过，直接拿来用

## **2.3 直接发逻辑分析** ##

给长度为m的数组arr，依次赋值，每次赋值前，都与前面已经赋值的数进行比较是否重复，若重复，则重复生成随机数赋值，若不存在，直接赋值。

## **2.4 两种方法实现代码如下** ##

package 随机不重复数组;
    //用于产生m个在0-N范围内的无重复的随机数(不包含N)
    
    import java.util.Arrays;
    
    public class Test1 {
        public static void main(String[] args) {
            //测试--产生20个在0-30范围内的无重复的随机数
            int num=20;
            int scope=30;//即取[0,19)中的整数
    
            //方法一测试
            int[] testArr=getRandomArrayByIndex(num, scope);
            System.out.println("方法一测试结果："+Arrays.toString(testArr));
    
            //方法二测试
            int[] test2Arr=getRandomArrayByValue(num, scope);
            System.out.println("方法二测试结果："+Arrays.toString(test2Arr));
    
    
        }
    
        //方法一：间接取值--实例化指定范围内所有值--再用随机下标求值
        //参数说明：num--无重复随机数的个数   scope--随机数所在范围(不包含scope)
        public static int[] getRandomArrayByIndex(int num,int scope){
            //1.获取scope范围内的所有数值，并存到数组中
            int[] randomArray=new int[scope];
            for(int i=0;i<randomArray.length;i++){
                randomArray[i]=i;
            }
    
            //2.从数组random中取数据，取过后的数改为-1 
            int[] numArray=new int[num];//存储num个随机数
            int i=0;
            while(i<numArray.length){
                int index=(int)(Math.random()*scope);
                if(randomArray[index]!=-1){
                    numArray[i]=randomArray[index];
                    randomArray[index]=-1;
                    i++;
                }
            }
    
            return numArray;
        }
    
        //方法二：for循环直接取值
        public static int[] getRandomArrayByValue(int num,int scope){
            //创建存储num个随机数的数据
            int[] numArray=new int[num];
            int lucky;//存生成的随机数
    
            //是否继续
            boolean isContinue=true;
            for(int i=0;i<numArray.length;i++){
                do {
                    lucky=(int)(Math.random()*scope);//获得随机数
    
                    //判断数组中是否已经存在了这个随机数
                    //--存在返回true，重新生成随机数  --不存在，返回false，停止循环，将该值赋值给数组
                    isContinue=isExistence(numArray, lucky);
                } while (isContinue);
    
                numArray[i]=lucky;
            }
    
            return numArray;
        }
    
        //方法二的辅助方法
        public static boolean isExistence(int[] numArray,int lucky){
            for (int i : numArray) {
                if(i==lucky){
                    //存在返回true--生成新的随机数，直到随机数与放入数组numArray中的数不同为止
                    return true;
                }
            }
    
            return false;
        }
    }

**测试多次结果**

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

![这里写图片描述][SouthEast 2]

**方法优劣：**

方法一（间接法）：比较占内存，每次都需要将所有的随机数存在一个数组或集合中。但理解简单，操作简便。
    
    方法二（直接发）：占用内存更小，方法简洁

## **2.5 递归解法** ##

**逻辑分析：**

*  第一步：直接给采用随机数赋值–生成一个长度为m的随机数组arr
 *  第二步：对已经存有随机数的数组arr，进行去重，重新赋值

**优劣：**

该方法有许多重复判断，每次遇到重复的数后，需要将前面的数重新全部判断一遍是否重复。（不推荐，当然你也可以拿去优化一下）

--------------------

**代码如下：**

package 随机不重复数组;
    
    import java.util.Arrays;
    
    public class Test2 {
        public static void main(String[] args) {
            // 测试--产生15个在0-30范围内的无重复的随机数
            int num = 15;
            int scope = 30;// 即取[0,19)中的整数
            // 方法三测试
            //创建随机数组：直接赋值随机数
            int[] numArray = new int[num];
            for (int i : numArray) {
                i = (int) (Math.random() * scope);
            }
    
            int[] test3Arr = isEqual(numArray, scope);
            System.out.println("方法三测试结果：" + Arrays.toString(test3Arr));
        }
    
        // 方法三：递归直接取值
        public static int[] isEqual(int[] numArray, int scope) {
            // 获得随机数
            int random = (int) (Math.random() * scope);
    
            // 给数组赋值---外层：给数组元素依次赋值
            for (int i = 1; i <= numArray.length - 1; i++) {
                // 内层：每次赋值后，与前面的数值进行比较，是否有重复
    
                // 若重复，就重新生成随机数赋值---若无重复，就给下一个数赋值
                for (int j = 0; j <= i - 1; j++) {
                    // 判断是否有重复
                    if (numArray[i] == numArray[j]) {
                        // 有重复就重新赋值
                        numArray[i] = random;
                        // 对新赋的值，进行判断
                        isEqual(numArray, scope);
    
                        break;
                    }
                }
            }
            return numArray;
        }
    
    }

**运行结果**

![这里写图片描述][SouthEast 3]

![这里写图片描述][SouthEast 4]

[SouthEast]: /images/20220614/9967dd74c4514229bfe74f773a1eaf31.png
[SouthEast 1]: /images/20220614/09c68825872e4876928f5ab678b8de0b.png
[SouthEast 2]: /images/20220614/beb1640afe0f4baaa4d7dfbed42238ff.png
[SouthEast 3]: /images/20220614/a11bd437baad4a5f8e2c4808b94fbf55.png
[SouthEast 4]: /images/20220614/07c1c3c416d243728d0d1416bb396676.png