Summary of methods for generating non-repeating random numbers in java

This article will introduce to you how to implement the function of random non-repeating numbers in JAVA. (Related video course recommendations: java video tutorial)

In order to better understand the meaning of this question, let’s first look at the specific content: Generate a random array of 1-100, but the array The numbers in cannot be repeated, that is, the positions are random, but the array elements cannot be repeated.

Here, the length of the array is not specified for us, we can make it any length between 1-100.

Next let us look at several implementation methods and compare these methods.

Usually we will use ArrayList or array to implement it. Let’s first look at the ArrayList implementation process, as shown in the following code:

import java.util.ArrayList;
import java.util.Random;

/**
 * 使用ArrayList实现
 * @Description: 
 * @File: Demo.java
 * @Date 2012-10-18 下午06:16:55
 * @Version V1.0
 */
public class Demo {
    public static void main(String[] args) {
        Object[] values = new Object[20];
        Random random = new Random();
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i = 0; i < values.length;i++){
            int number = random.nextInt(100) + 1;
            
            if(!list.contains(number)){
                list.add(number);
            }
        }
        
        values = list.toArray();
        
        // 遍历数组并打印数据
        for(int i = 0;i < values.length;i++){
            System.out.print(values[i] + "\t");
            
            if(( i + 1 ) % 10 == 0){
                System.out.println("\n");
            }
        }
    }
}

The process of using array implementation is as follows:

import java.util.Random;

/**
 * 使用数组实现
 * @Description: 

 * @File: Demo4.java

 * @Package None

 * @Author Hanyonglu

 * @Date 2012-10-18 下午06:27:38

 * @Version V1.0
 */
public class Demo4 {
    public static void main(String[] args) {
        int[] values = new int[20];
        Random random = new Random();
        
        for(int i = 0;i < values.length;i++){
            int number = random.nextInt(100) + 1;
            
            for(int j = 0;j <= i;j++){
                if(number != values[j]){
                    values[i]=number;
                }                              
            }
        }
        
        // 遍历数组并打印数据
        for(int i = 0;i < values.length;i++){
            System.out.print(values[i] + "\t");
            
            if(( i + 1 ) % 10 == 0){
                System.out.println("\n");
            }
        }
    }
}

The above two implementation processes are relatively inefficient. Because every time you add it, you have to traverse whether the number exists in the current list, and the time complexity is O(N^2). We can think about it this way: Since it involves no duplication, we can think about the functions of HashSet and HashMap.

HashSet implements the Set interface. The mathematical definition of Set is a collection without duplication and order. HashMap implements Map and does not allow duplicate Keys. In this way we can use HashMap or HashSet to achieve it.

When using HashMap to implement, you only need to convert its key into an array, as shown in the following code:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;
import java.util.Map.Entry;

/**
 * 使用HashMap实现
 * @Description: 

 * @File: Demo.java

 * @Package None

 * @Author Hanyonglu

 * @Date 2012-10-18 下午06:12:50

 * @Version V1.0
 */
public class Demo {
    public static void main(String[] args) {
        int n = 0;
        Object[] values = new Object[20];
        
        Random random = new Random();
        HashMap<Object, Object> hashMap = new HashMap<Object, Object>();
        
        // 生成随机数字并存入HashMap
        for(int i = 0;i < values.length;i++){
            int number = random.nextInt(100) + 1;
            hashMap.put(number, i);
        }
        
        // 从HashMap导入数组
        values = hashMap.keySet().toArray();
        
        // 遍历数组并打印数据
        for(int i = 0;i < values.length;i++){
            System.out.print(values[i] + "\t");
            
            if(( i + 1 ) % 10 == 0){
                System.out.println("\n");
            }
        }
        
//        Iterator iter = hashMap.entrySet().iterator();
//        // 遍历HashMap
//        while (iter.hasNext()) {
//            Entry<Integer, Integer> entry = (Entry)iter.next();
//            int key = entry.getKey();
//            n++;
//            
//            System.out.print(key + "\t");
//            
//            if(n % 10 == 0){
//                System.out.println("\n");
//            }
//        }
    }
}

Since the relationship between HashSet and HashMap is too close, HashSet is used at the bottom layer HashMap is implemented, but there is no Value collection, only a Key collection, so it can also be implemented using HashSet, as shown in the following code:

import java.util.HashSet;
import java.util.Random;

/**
 * 使用HashSet实现
 * @Description: 

 * @File: Test.java

 * @Package None

 * @Author Hanyonglu

 * @Date 2012-10-18 下午06:11:41

 * @Version V1.0
 */
public class Test {
    public static void main(String[] args) {
        Random random = new Random();
        Object[] values = new Object[20];
        HashSet<Integer> hashSet = new HashSet<Integer>();
        
        // 生成随机数字并存入HashSet
        for(int i = 0;i < values.length;i++){
            int number = random.nextInt(100) + 1;
            hashSet.add(number);
        }
        
        values = hashSet.toArray();
        
        // 遍历数组并打印数据
        for(int i = 0;i < values.length;i++){
            System.out.print(values[i] + "\t");
            
            if(( i + 1 ) % 10 == 0){
                System.out.println("\n");
            }
        }
    }
}

This implementation is slightly more efficient. If we limit the length of the array, we only need to change the for loop and set it to a whlie loop. As shown below:

import java.util.HashSet;
import java.util.Random;

/**
 * 使用HashSet实现
 * @Description: 

 * @File: Test.java

 * @Package None

 * @Author Hanyonglu

 * @Date 2012-10-18 下午05:11:41

 * @Version V1.0
 */
public class Test {
    public static void main(String[] args) {
        Random random = new Random();
        Object[] values = new Object[20];
        HashSet<Integer> hashSet = new HashSet<Integer>();
        
        // 生成随机数字并存入HashSet
        while(hashSet.size() < values.length){
            hashSet.add(random.nextInt(100) + 1);
        }
        
        values = hashSet.toArray();
        
        // 遍历数组并打印数据
        for(int i = 0;i < values.length;i++){
            System.out.print(values[i] + "\t");
            
            if(( i + 1 ) % 10 == 0){
                System.out.println("\n");
            }
        }
    }
}

Compared with the above, the efficiency of using HashMap is relatively high. In fact, it is HashSet, then array, and finally ArrayList. If we generate 10,000 pieces of data, we will find that the time spent using HashMap is: 0.05s, HashSet is 0.07s, array is: 0.20s, and ArrayList is 0.25s. If you are interested, you can set a time to check it out.

Of course, in addition to using HashMap, there are other efficient methods. For example, we can store the numbers 1-100 in an array, and then randomly generate two subscripts in the for loop. If the two subscripts are not equal, we can exchange the elements in the array. The implementation process is as follows ：

import java.util.Random;

/**
 * 随机调换位置实现
 * @Description: 

 * @File: Demo4.java

 * @Package None

 * @Author Hanyonglu

 * @Date 2012-10-18 下午06:54:06

 * @Version V1.0
 */
public class Demo4 {
    public static void main(String[] args) {
        int values[] = new int[100];   
        int temp1,temp2,temp3;   
        Random r = new Random();   
        
        for(int i = 0;i < values.length;i++){
            values[i] = i + 1;
        }
        
        //随机交换values.length次   
        for(int i = 0;i < values.length;i++){   
            temp1 = Math.abs(r.nextInt()) % (values.length-1); //随机产生一个位置   
            temp2 = Math.abs(r.nextInt()) % (values.length-1); //随机产生另一个位置   
            
            if(temp1 != temp2){
                temp3 = values[temp1];   
                values[temp1] = values[temp2];   
                values[temp2] = temp3;
            } 
        }   
        
        // 遍历数组并打印数据
        for(int i = 0;i < 20;i++){
            System.out.print(values[i] + "\t");
            
            if(( i + 1 ) % 10 == 0){
                System.out.println("\n");
            }
        }
    }
}

For more java related articles, please pay attention to java basic tutorial.

The above is the detailed content of Summary of methods for generating non-repeating random numbers in java. For more information, please follow other related articles on the PHP Chinese website!