生成不重复随机数的算法

### 生成不重复随机数的算法 在许多应用领域中，比如在线考试系统、游戏开发或是数据处理等场景，生成不重复的随机数是一项非常重要的技术。本文将详细介绍几种不同的方法来实现这一功能，并通过具体的Java代码示例来进行说明。 #### 方法一：使用布尔数组标记法 这种方法的基本思想是利用一个布尔数组来标记已经生成过的随机数，确保不会重复生成相同的数值。具体步骤如下： 1. 初始化一个布尔数组`bool[]`和一个整型变量`num`。 2. 使用`Random`类生成一个随机数`num`。 3. 通过布尔数组检查该随机数是否已经被标记为已生成，如果没有，则添加到结果列表中，并在布尔数组中将其标记为已生成。 4. 重复步骤2-3，直到生成足够的随机数为止。 **示例代码**: ```java import java.util.*; public class Test { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); int n = 10; Random rand = new Random(); boolean[] bool = new boolean[n]; int num = 0; for (int i = 0; i < n; i++) { do { // 生成随机数 num = rand.nextInt(n); } while (bool[num]); bool[num] = true; list.add(num); } System.out.println(list); } } ``` #### 方法二：使用数组和双重循环检测法 这种方法通过预先定义一个固定大小的数组，然后在生成随机数的过程中使用双重循环来检查是否已经有重复的值。如果发现重复，则重新生成，直至数组填充完成。 **示例代码**: ```java public class Test { public static void main(String[] args) { int[] arr = new int[10]; for (int i = 0; i < 10; i++) { arr[i] = (int) (Math.random() * 40) + 1; for (int j = 0; j < i; j++) { if (arr[j] == arr[i]) { i--; break; } } } for (int i = 0; i < 10; i++) { System.out.print(arr[i] + " "); } } } ``` #### 方法三：Fisher-Yates洗牌算法 Fisher-Yates洗牌算法是一种有效的生成不重复随机数的方法。它通过对数组进行随机交换来达到目的。 **示例代码**: ```java import java.util.*; public class Test { public static void main(String[] args) { int n = 40; int[] num = new int[n]; for (int i = 0; i < num.length; i++) { num[i] = i + 1; } int[] arr = new int[10]; for (int i = 0; i < arr.length; i++) { int r = (int) (Math.random() * n); arr[i] = num[r]; num[r] = num[n - 1]; n--; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } } ``` #### 方法四：使用`LinkedList`和`remove`方法 这种方法使用`LinkedList`来存储可选的数字，每次从列表中移除一个随机元素，从而确保生成的随机数不会重复。 **示例代码**: ```java import java.util.*; public class Test { public static void main(String[] args) { LinkedList<Integer> myList = new LinkedList<>(); int n = 40; for (int i = 0; i < n; i++) { myList.add(i + 1); } int[] arr = new int[10]; for (int i = 0; i < arr.length; i++) { arr[i] = myList.remove((int) (Math.random() * n)); n--; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } } ``` #### 方法五：使用`Set`结构 使用`Set`结构可以自动去除重复项，因此非常适合用于生成不重复的随机数。 **示例代码**: ```java import java.util.*; public class Test { public static void main(String[] args) { Set<Integer> mySet = new LinkedHashSet<>(); while (mySet.size() < 10) { mySet.add((int) (Math.random() * 40 + 1)); } for (Integer i : mySet) { System.out.print(i + " "); } } } ``` #### 方法六：基于数组的替换算法 这种方法通过创建一个初始有序数组，然后使用随机交换的方式来生成不重复的随机数。 **示例代码**: ```java public static int[] randoms() { Random r = new Random(); int temp1, temp2; int send[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}; int len = send.length; int returnValue[] = new int[22]; for (int i = 0; i < 22; i++) { temp1 = Math.abs(r.nextInt()) % len; returnValue[i] = send[temp1]; temp2 = send[temp1]; send[temp1] = send[len - 1]; send[len - 1] = temp2; len--; } return returnValue; } ``` 以上各种方法各有优缺点，选择哪种方法取决于具体的应用场景和需求。例如，对于需要高效生成大量随机数的情况，建议采用Fisher-Yates洗牌算法或基于`Set`结构的方法；而对于简单的小规模应用，使用布尔数组标记法可能更为合适。