怎么产生0至n-1之间k个不同的随机顺序的随机整数

如何产生0至n-1之间k个不同的随机顺序的随机整数

如题，不知大家有什么好的想法，比如n = 10000000 ,求1000000个小于n的随机数，这些数不重复，顺序是乱的。

谢谢。
[最优解释]

public static void main(String[] args) {
    int n = 10000000, k = 1000000;
    boolean[] appear = new boolean[n];
    Random r = new Random();
    int[] nums = new int[k];
    for (int i = 0; i &lt; k; i++) {
        int j = -1;
        while (appear[j = r.nextInt(n)]);
        nums[i] = j;
        //appear[j] = true;System.out.println(nums[i]);
    }
}

[其他解释]
在文件里存1-n个连续的数，用换行符隔开。
随机生成一个小于n的数，作为行号去文件里取，取后删除同时n-1

如果不考虑n的大小，用Collection.shuffle内存乱序一下即可。
[其他解释]
既然是顺序是乱的(Set)，那每次随意拿一个出来,然后remove掉不就行了。
[其他解释]

package com;

import java.util.ArrayList;
import java.util.List;

public class B {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List list=new ArrayList&lt;Integer&gt;();
        for(int i=1;i&lt;=10000000;i++){
            list.add(i);
        }
        long start=System.currentTimeMillis();
        java.util.Collections.shuffle(list);
        
        System.out.println(System.currentTimeMillis()-start);
    }

}

[其他解释]
用random去随机数
添加到set中
如果set的size（）小于n-1就继续调用此方法
[其他解释]

public static void main(String[] args) {
    int n = 10000000, k = 1000000;
    int[] arr = new int[n];
    for (int i = 0; i &lt; n; i++)
        arr[i] = i;
    Random r = new Random();
    int[] nums = new int[k];
    for (int i = 0; i &lt; k; i++) {
        int j = r.nextInt(n - i) + i;
        nums[i] = arr[j];
        arr[j] = arr[i]; 
 
    }
}

再来一个……
[其他解释]
楼主的意思就是生成1-n随机的整数吧？方法很多的


package com;

import java.util.ArrayList;
import java.util.List;

public class Test4 {

/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
List list = new ArrayList&lt;Integer&gt;();

for (int i = 1; i &lt;= 54; i++) {
list.add(i);
}

while (list.size() &gt; 0) {
int size = list.size();
int r = (int) (java.lang.Math.random() * size);
System.out.println(list.get(r));
list.remove(r);
}
}

}

[其他解释]
该回复于2010-09-17 10:23:18被版主删除
[其他解释]
谢谢楼上兄弟们深夜的回复。

2楼的兄弟,貌似list里面的元素个数不要那么多，list里面元素的个数应该是另外指定的。

3楼：这个是最简单的方法，也可能是最耗时的方法。

大家有没有更好的想法啊。要考虑时间和空间啊。
[其他解释]
就用#3楼的的了
[其他解释]
数字大了就有点扛不住了给大家都看看吧
import java.lang.Math;
import java.util.Vector;
import java.util.Random;
public class Test
{
final static int k=100;
int num=-1;
public Test(int num)
{
this.num=num;
}
public int getnum()
{
return this.num;
}
public void setnum(int num)
{
this.num=num;
}
public static void main(String[] args)
{
Vector v=new Vector();
Vector r=new Vector();
for(int i=0;i<k;i++)
{
v.addElement(new Test(i));
}
do
{
Random generator = new Random();
int n = generator.nextInt(v.size());
Test tn=(Test) v.elementAt(n);
if(v.contains(tn))
{
int h=tn.getnum();
v.remove(n);

r.addElement(new Test(h));
}

}while(r.size()<k);

//System.out.println(r.size());

for(int j=0;j<r.size();j++)
{
Test tj=(Test)r.elementAt(j);
System.out.println(tj.getnum());
}

}
}
[其他解释]
经典的洗牌算法。
[其他解释]

引用:

既然是顺序是乱的(Set)，那每次随意拿一个出来,然后remove掉不就行了。

n = 10000000(一千万) ，求k个0至n之间的随机数,随机数小于n,求出的数据没有重复。
[其他解释]

引用:

Java code
package com;

import java.util.ArrayList;
import java.util.List;

public class B {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-gen……

不好意思，我不该把一千万和一百万写在一起，随机数的个数不是一千万，而是任意指定的，当然个数小于一千万，而且随机数的值小于一千万。
[其他解释]

引用:

就用#3楼的的了

三楼兄弟的估计有点占内存和时间


public static void main(String[] args) {
long start = System.currentTimeMillis();
int n = 10000000;
int k = 9000000;
Set&lt;Integer&gt; set = new HashSet&lt;Integer&gt;();
Random rand = new Random();
while (set.size() &lt; k) {
set.add(rand.nextInt(n));
}
System.out.println("set's size :" + set.size()) ;
System.out.println(System.currentTimeMillis() - start);
}

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.HashMap.addEntry(HashMap.java:753)
at java.util.HashMap.put(HashMap.java:385)
at java.util.HashSet.add(HashSet.java:200)
at chapter1.CreateRandomNum.main(CreateRandomNum.java:19)

用泛型和不用泛型都试了。

[其他解释]
终于搞懂你意思了


package com;

import java.util.ArrayList;
import java.util.List;

public class Test2 {

/**
 * @param args
 */

public static void main(String[] args) {
// TODO Auto-generated method stub
List list = new ArrayList&lt;Integer&gt;();

for (int i = 1; i &lt;= 10000000; i++) {
list.add(i);
}
while (list.size() &gt; 9000000) {
int size = list.size();
int r = (int) (java.lang.Math.random() * size);
System.out.println(list.get(r));
list.remove(r);

}
} 
 

}

[其他解释]
这个你可以想象成1000W张牌，只发100W张牌，梭哈打法哈
[其他解释]
学习了
[其他解释]

引用:

用list和set开销其实都挺大的……
你可以看下6楼和8楼我的两个解法
6楼的方法是将每个数是否已出现存入布尔数组，如果已出现则对应项设为true，然后随机时如果随即到的项已经是true则继续直到随机到的项为false为止
8楼的方法是将所有数存入整数数组，如果第i次随机到某数则将它与第i项交换，随机范围是i到n-1，i的范围从0到k-1，也就是重复执行k次

非常感谢这位热心的兄弟，上周我看了你的回复，也运行了你的程序，确实花费的时间很短，而且没有内存溢出。


public static void main(String[] args) {
long start = System.currentTimeMillis();
int n = 10000000;
int k = 1000000;
boolean[] appear = new boolean[n];
Random rand = new Random();
int [] jj = new int [k];
for (int i = 0 ; i &lt; k ; i ++) {
int j = -1 ;
while (appear[j = rand.nextInt(n)]);
jj[i] = j; 
appear[j] = true;
}

System.out.println("jj'length:" + jj.length);
System.out.println(System.currentTimeMillis() - start);
}

一般运行时间在100-200毫秒之间。再次感谢。
[其他解释]
用list和set开销其实都挺大的……
你可以看下6楼和8楼我的两个解法
6楼的方法是将每个数是否已出现存入布尔数组，如果已出现则对应项设为true，然后随机时如果随即到的项已经是true则继续直到随机到的项为false为止
8楼的方法是将所有数存入整数数组，如果第i次随机到某数则将它与第i项交换，随机范围是i到n-1，i的范围从0到k-1，也就是重复执行k次
[其他解释]
交换的不错
[其他解释]
还等几个回复就准备结贴了，嘎嘎。
[其他解释]

引用:

既然是顺序是乱的(Set)，那每次随意拿一个出来,然后remove掉不就行了。

对的
[其他解释]
public static int[] getRandom()
{
int n = 10000;
int k = 9000;
boolean[] appear = new boolean[n];
Random random = new Random();
int result[] = new int[k];
for (int i = 0; i < k; i++)
{

int a = random.nextInt(n);
if (appear[a]==false)
{
result[i] = a;
appear[a] = true;
}
}
return result;
}
[其他解释]
帮顶没看懂楼主的意思
------其他解决方案--------------------

学习学习
[其他解释]

引用:

帮顶没看懂楼主的意思

比如我指定n=100,我想随机生成k=80个随机数, 每个随机数都在0---n之间，生成的随机数序列不能有重复的。

n和k数值比较小的时候还好，当n=一千万，k=几百万时，要考虑速度和性能。
[其他解释]

引用:

引用:
既然是顺序是乱的(Set)，那每次随意拿一个出来,然后remove掉不就行了。

对的

这种方法确实可以，但依赖于java 的set容器，数据量多的话，耗内存比较多。速度也比较慢。

[其他解释]
楼主，8楼兄弟的方法生成随机数 int j = r.nextInt(n - i) + i;改为int j = r.nextInt(n)就不行了，这是为什么啊。它们有什么区别啊

怎么产生0至n-1之间k个不同的随机顺序

热点推荐