/**
*
*問題或許可以是這樣:產(chǎn)生m個隨機(jī)正整數(shù),要求范圍是從1到n,平且它們互不相同。
問題或許可以這樣解決:
假設(shè)我們已經(jīng)有了經(jīng)過排序的(升序),且滿足要求的k個正整數(shù),我們繼續(xù):
1、在從1到n-k的區(qū)間范圍內(nèi),產(chǎn)生一個隨機(jī)的正整數(shù)i1;
2、統(tǒng)計在已有序列中比i1小的數(shù),將其個數(shù)加到i1上,得到i2;再統(tǒng)計從i1到i2數(shù)的個數(shù),得到i3;一直循環(huán),直到i不變?yōu)橹埂H缓螅裪插入已有的序列。這個過程相當(dāng)于從頭數(shù)出i1個空白,以此來保證新的數(shù)是隨機(jī)的。
3、這時得到了k+1個滿足要求的數(shù),然后就循環(huán)吧。
上面的方法適用于n很大,但是m很小的時候。
如果m和n都很大,并且希望一次性的產(chǎn)生,那么:
1先產(chǎn)生有一定冗余的隨機(jī)正整數(shù),然后排序,然后去掉相同的數(shù)。
如果,產(chǎn)生了超額的數(shù),可以將數(shù)列再打亂順序,然后,取出符合規(guī)定的數(shù)目的數(shù)。
當(dāng)然,也可以兩種方法相結(jié)合,就是:
1、先產(chǎn)生超過需求的、有一定冗余的隨機(jī)正整數(shù),然后排序,然后去掉相同的數(shù),并且保存下來。記錄它的數(shù)目m1 >m;
2、當(dāng)要用時,在產(chǎn)生一個從1到m的隨機(jī)數(shù)j,然后取出數(shù)據(jù)庫中第j個數(shù),輸出,并且把它從數(shù)據(jù)庫中刪除到。
*
*
*
*
*
*
*
*
*數(shù)據(jù)有點(diǎn)大,用了128m
start_1 (); 是即時輸出(因?yàn)橛胋oolean數(shù)組,所以內(nèi)存小得多)
start_2 (); 是把數(shù)據(jù)存進(jìn)數(shù)組,以便再處理(需要內(nèi)存很大,不贊成使用)
如果要處理數(shù)據(jù),可以用 start_1 (); 把數(shù)據(jù)保存進(jìn)文件,再從文件中讀取數(shù)據(jù)進(jìn)行處理。
*/
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() {
//布朗型默認(rèn)為 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() {
//整型默認(rèn)為 0
int[] iarr = new int[n];
//
java.util.Random r = new java.util.Random ();
int j = 0, x;
int m = n;
//少循環(huán)一次,因?yàn)橐?0
while(j < m-1) {
x = r.nextInt (n);
if (iarr[x] == 0) {
j++;
iarr[x] = j;
}
}
}
}
/*
*上面的算法,沒有優(yōu)化,生成數(shù)據(jù)耗時間。
下面的算法改進(jìn)了一下。生成所有數(shù)據(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 ();
}
*/
/*
*和一位仁兄在另一個帖子爭論中,受到啟發(fā)。
終于悟出一種時間復(fù)雜度極低的算法。
(可以證明,任意一個數(shù) 在 任意位置的概率 都為 1/n)
因?yàn)閮?nèi)存不夠,所以改成了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];
}
*/