10000个球中随机取出1000个球

前几天看到一个算法题，说有10000个球，从中随机取出1000个，要求高性能？

 

 

刚开始我的想法是，循环0-1000 每次在0-10000中产生随机数，如果map中不存在，就放入map中，基数加1，如果存在，不加。这个方式基本能实现，但是效率不高，而且理论上有可能死循环。

 

还有一个方式就是，循环1000次，每次产生0-9的随机数，然后基数*10+随机数，存入map中。这样1000次肯定产生不同的球，第二个算法就是每次概率减少1/1000，最后一个概率只有1/10.而前一种最后一个是1/9001.

 

周末无聊，学python，顺便来一个python实现

 

 

import random

map = {}
for i in range(0,1000):
    t = random.randint(i*10,i*10+9)
    map[t]=t

for k in map.iterkeys():
    print k

评论

4 楼 lavafree 2011-03-07  

zcsuntt 写道

for(i = 0; i < 10000; i++)
{
x[i] = i;
}
for(i = 0; i < 1000; i++)
{
t = rand(i,10000-1);
swap(x[i], x[t]);
out(x[i]);
}

既然是从10000个球中区出1000个，所以取出的球可定不能重复，你的代码可定有问题，比如第一次随机数是100，第二次随机数还是100。还有，你第一次循环10000次，第二次又循环1000次，还要做交换，代码效率极差！

3 楼 lavafree 2011-03-07  

贫僧不吃肉 写道

7  * 10 + 20 == 6 * 10 + 30

不会出现你那种情况，每次i为i+1,而且随机数是在0-9范围内。

2 楼 zcsuntt 2011-03-07  

for(i = 0; i < 10000; i++)
{
x[i] = i;
}
for(i = 0; i < 1000; i++)
{
t = rand(i,10000-1);
swap(x[i], x[t]);
out(x[i]);
}

1 楼 贫僧不吃肉 2011-03-06  

7  * 10 + 20 == 6 * 10 + 30