/**
 *
 *問題或許可以是這樣：產(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)橹埂Ｈ缓螅裪插入已有的序列。這個過程相當(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];
   
}
*/