问题描述：
给定输入N，生成从1开始的：1，2，3，4，......N 一组随机序列，序列中的数不能重复出现。
比如：N=5，合法的随机序列为{4,3,1,5,2} 、{3,1,4,2,5}……非法的序列有{5,4,1,2,1}
来源：《数据结构与算法分析-MAW著 第二章习题2.8》
思路1：
对于数据a[N]而言，当随机生成第i个数a[i]时，确保a[i]在 a[0]至a[i-1]中没有出现过，就把该数放入a[i]，继续生成下一个数a[i+1]
算法复杂度为O(N^2logN)---每生成一个a[i]，需要扫描a[0]...a[i-1]。
public static int[] algorithm1(int N) { int []a = new int[N]; for (int i = 0; i < a.length; ++i) { while (true) { a[i] = randInt(1, N); //生成[1,N]之间的一个随机数
int j = 0; for (; j < i; ++j) { if (a[i] == a[j]) { break;//如果这个随机数已经在前面出现过了,break,下一轮继续生成另一个随机数,直至a[i]与前面所有的数不同 } } //end for if(j == i) break;//本次生成的a[i]在前面没有出现过, break while, i++,下一轮生成a[i+1] }//end while } return a; }
思路2：
先以1,2,3,.....N 初始化数组a[N]，然后随机选择一个数组下标，交换这两个下标处的值。
算法复杂度为O(N)
public static int[] algorithm3(int N){ int[] a = new int[N]; for(int i = 1; i <= N; i++) a[i-1] = i; for(int i = 1; i < N; i++) swapReference(a, i, randInt(0, i)); return a; } private static void swapReference(int[] a, int i, int j){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
JAVA中采用java.util.Random类的nextInt(int n)方法可生成一个[0,n)的随机数。---包括0不包括n
要生成范围[i,j]内的一个随机数，方法如下：
①nextInt(j-i+1)----生成[0, j-i+1)之间的随机数
②nextInt(j-i+1)+i 生成 [i, j+1)之间的随机数，即为[i,j]内的一个随机数了。
性能比较：当N=1w时，algorithm1用时42ms，algorithm3用时2ms
当N=10w时，algorithm1用时2806ms，algorithm3用时12ms
整个程序代码如下：
import java.util.Random; public class C2_2_8 { private static Random rand = new Random(47); //生成一个[i,j]之间的随机数 public static int randInt(int i, int j){ return rand.nextInt(j-i+1) + i; } public static int[] algorithm1(int N) { int []a = new int[N]; for (int i = 0; i < a.length; ++i) { while (true) { a[i] = randInt(1, N); //生成[1,N]之间的一个随机数 for (int j = 0; j < i; ++j) { if (a[i] == a[j]) { break;//如果这个随机数已经在前面出现过了,break,下一轮继续生成另一个随机数,直至a[i]与前面所有的数不同 } } //end for break;//本次生成的a[i]在前面没有出现过, break while, i++,下一轮生成a[i+1] }//end while } return a; } public static int[] algorithm3(int N){ int[] a = new int[N]; for(int i = 1; i <= N; i++) a[i-1] = i; for(int i = 1; i < N; i++) swapReference(a, i, randInt(0, i)); return a; }
//生成一个即有正数又有负数的随机数组
public static int[] randomArr(int N){
int [] a = new int[N];
for(int i = 1; i <= N/2; i++)
a[i-1] = i;
for(int j = N; j > N/2; j--)
a[j-1] = -j;
for(int i = 1; i < N; i++)
swapReference(a, i, randInt(0, i));
return a;
} private static void swapReference(int[] a, int i, int j){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } public static void main(String[] args) { long start3 = System.currentTimeMillis(); algorithm3(100000); System.out.println(System.currentTimeMillis() - start3); long start = System.currentTimeMillis(); algorithm1(100000); long time = System.currentTimeMillis() - start; System.out.println(time); } }
