如何生成100个1-100以内的不重复的随机数

这是个经典的面试题目：生成长度为100的数组，插入1-100以内的但均不重复的随机数

一、简单实现思路:

(1) 把N个数放入Hashtable 或者arrayList 中.

(2) 从上面的集合中随机抽取一个数放入int数组中.

(3) 把取出的这个数从上面的集合中删除.

(4) 循环 (2),(3) 步骤,直到int数组取满为止.

这是一种比较简单的实现思路，实现代码如下：

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

public class Main {
	private static int range = 100;
	private static ArrayList<Integer> originalList = new ArrayList<Integer>();
	private static ArrayList<Integer> result = new ArrayList<Integer>();

	static {
		for (int i = 1; i <= range; i++) {
			originalList.add(i);
		}
	}

	public static void main(String args[]) {
		for (int i = 0; i < range; i++) {
			int j = range - i;
			int r = (int) (new Random().nextInt(j));

			result.add(originalList.get(r));

			System.out.print(originalList.get(r) + ", ");
			originalList.remove(r);
		}

		Collections.sort(result);
		System.out.println("\n\n生成的数组大小是：" + result.size() + "------以下是排序结果，看是否有重复的随机数");
		for (Integer i : result) {
			System.out.print(i + ", ");
		}
	}
}

执行结果如下：

74, 75, 47, 76, 59, 94, 2, 33, 23, 66, 60, 13, 44, 34, 7, 92, 11, 86, 4, 38, 26, 55, 64, 99, 1, 54, 30, 72, 80, 87, 15, 24, 25, 37, 83, 49, 28, 81, 79, 35, 18, 68, 61, 46, 98, 58, 85, 29, 39, 48, 53, 14, 8, 91, 42, 36, 65, 62, 6, 52, 21, 78, 63, 73, 16, 88, 5, 69, 19, 51, 50, 43, 40, 70, 89, 10, 12, 71, 96, 45, 93, 9, 31, 22, 95, 20, 17, 3, 67, 90, 41, 82, 57, 84, 100, 32, 77, 27, 97, 56, 

生成的数组大小是：100------以下是排序结果，看是否有重复的随机数
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100,

二、改进算法

我们一般都会想到这种做法,但是当Hashtable或者ArrayList中放几千万,几亿数据时,这时从集合中删除元素将严重影响性能,如果突破此瓶颈? 网上找到一种更好的方法.

(1) 把N个数放到容器A(int数组)中.
(2) 从N个数中随机取出1个数放入容器B(int数组)中.
(3) 把容器A中最后一个数与随机抽取的数对调 或者 把容器A中最后一个数覆盖随机抽取出来的数.
(4) 这时从容器A(假设N个数,索引0 到 索引N-2)之间随机取一个数.再放入容器B中,重复此步骤.

说明：也就是第二次是从容器A中 第一个元素到倒数第二个元素 中随机取一个数.
这种好处是,随机数所取范围逐步缩小,而且杜绝了大数据时集合执行删除操作时产生的瓶颈.

所以，向下面这样实现会更好：

public class Main {
	private static int range = 100;
	private static int[] result;

	public static void main(String args[]) {
		result = getNumber(range);
		for (int i = 0; i < range; i++) {
			System.out.print(result[i] + ", ");
		}
	}
	
	public static int[] getNumber(int total){
		int[] NumberBox = new int[total];			//容器A
		int[] rtnNumber = new int[total];			//容器B

		for (int i = 0; i < total; i++){
		  NumberBox[i] = i;		//先把N个数放入容器A中
		}
		int end = total - 1;
		
		for (int j = 0; j < total; j++){
		  int num = new Random().nextInt(end + 1);	//取随机数
		  rtnNumber[j] = NumberBox[num];			//把随机数放入容器B
		  NumberBox[num] = NumberBox[end];			//把容器A中最后一个数覆盖所取的随机数
		  end--;									//缩小随机数所取范围
		}
		return rtnNumber;							//返回int型数组
	}
}

执行结果如下：

80, 9, 70, 22, 3, 63, 12, 81, 73, 41, 90, 83, 27, 71, 88, 5, 40, 18, 25, 37, 55, 60, 93, 87, 17, 89, 99, 84, 32, 96, 62, 98, 77, 30, 23, 35, 47, 24, 21, 53, 95, 7, 85, 2, 65, 1, 39, 43, 76, 46, 42, 91, 4, 26, 52, 86, 34, 54, 38, 78, 31, 11, 66, 36, 50, 75, 16, 68, 56, 33, 48, 15, 74, 69, 49, 6, 58, 10, 29, 92, 64, 59, 28, 61, 45, 19, 14, 13, 44, 72, 94, 20, 97, 51, 67, 79, 0, 82, 8, 57,