/**
*
*问题或许可以是这样：产生m个随机正整数，要求范围是从1到n，平且它们互不相同。
问题或许可以这样解决：
假设我们已经有了经过排序的（升序），且满足要求的k个正整数，我们继续：
1、在从1到n-k的区间范围内，产生一个随机的正整数i1；
2、统计在已有序列中比i1小的数，将其个数加到i1上，得到i2；再统计从i1到i2数的个数，得到i3；一直循环，直到i不变为止。然后，把i插入已有的序列。这个过程相当于从头数出i1个空白，以此来保证新的数是随机的。
3、这时得到了k+1个满足要求的数，然后就循环吧。
上面的方法适用于n很大，但是m很小的时候。
如果m和n都很大，并且希望一次性的产生，那么：
1先产生有一定冗余的随机正整数，然后排序，然后去掉相同的数。
如果，产生了超额的数，可以将数列再打乱顺序，然后，取出符合规定的数目的数。
当然，也可以两种方法相结合，就是：
1、先产生超过需求的、有一定冗余的随机正整数，然后排序，然后去掉相同的数，并且保存下来。记录它的数目m1 >m；
2、当要用时，在产生一个从1到m的随机数j，然后取出数据库中第j个数，输出，并且把它从数据库中删除到。
*
*
*
*
*
*
*
*
*数据有点大，用了128m
start_1 (); 是即时输出（因为用boolean数组，所以内存小得多）
start_2 (); 是把数据存进数组，以便再处理（需要内存很大，不赞成使用）
如果要处理数据，可以用 start_1 (); 把数据保存进文件，再从文件中读取数据进行处理。
*/
public class Main{
public final int n = 10000000;
public Main () {
start_1();
//start_2 ();
}
public static void main (String[] args) {
new Main();
}
public void start_1() {
//布朗型默认为 false
boolean[] barr = new boolean[n];
//
java.util.Random r = new java.util.Random ();
int j = 0, x;
int m = n;
while(j < m) {
x = r.nextInt (n);
if (! barr[x]) {
j++;
barr[x] = true;
System.out.println (x);
}
}
}
public void start_2() {
//整型默认为 0
int[] iarr = new int[n];
//
java.util.Random r = new java.util.Random ();
int j = 0, x;
int m = n;
//少循环一次，因为要生成 0
while(j < m-1) {
x = r.nextInt (n);
if (iarr[x] == 0) {
j++;
iarr[x] = j;
}
}
}
}
/*
*上面的算法，没有优化，生成数据耗时间。
下面的算法改进了一下。生成所有数据半分钟左右。
+----------
| 0...999999
| .
| .
| .
| 99
Java code
public class Main {
public Main () {
start_1 ();
start_2 ();
}
public static void main (String[] args) {
new Main ();
}
** void start_1 () {
for (int i = 0; i < n; i++) {
byte j = 0;
while(j < m-1) {
int x = r.nextInt (m);
if (barr_1[x] == 0) {
j++;
barr_1[x] = j;
}
}
}
}
** void start_2 () {
int j = 0;
while(j < n) {
int x = r.nextInt (n);
int y = (int) barr_2[x];
if (y < m) {
j++;
barr_2[x]++;
int z = ((int) barr_1[x][y]) * n;
//System.out.println (x + z);
}
}
}
** final int s = 10000*10000;
** final int m = 100;
** final int n = s/m;
** byte[][] barr_1 = new byte[n][m];
** byte[] barr_2 = new byte[n];
** java.util.Random r = new java.util.Random ();
}
*/
/*
*和一位仁兄在另一个帖子争论中，受到启发。
终于悟出一种时间复杂度极低的算法。
（可以证明，任意一个数 在 任意位置的概率 都为 1/n）
因为内存不够，所以改成了7个9来算。总时间2秒
Java code
public class Main {
public Main () {
start ();
}
public static void main (String args[]) {
new Main ();
}
** void start () {
java.util.Random r = new java.util.Random ();
for (int i = 0; i < n; i++) {
int x = r.nextInt (i+1);
iarr = iarr[x];
iarr[x] = i;
}
//
int m = 10;
for (int i = 0; i < m; i++) {
System.out.print (iarr + " ");
}
}
** final int n = 1000*10000;
** int[] iarr = new int[n];
}
*/
本文转自博客园执着的笨蛋的博客，原文链接：java 乱序（小汇），如需转载请自行联系原博主。
