10万个数字无序排列,要求不重复!高手进!!!

(PS:可能是我描述的不太清楚,其实意思就是这样的。依次生成10W个随机数填充到数组,随机数1-10W之间不能重复。嗯,对,本意就是这样。)

今天面试,技术总监给我出了个思考题,求随机10W个数字无序排列,如何才能高效的执行,内存没有要求,最好的硬件配置,伪代码如下:

static $arr = array();
for($i = 0; $i < 100000; $i++)
{
    $rand = rand(1,100000);
    $y = 0;
    while($rand == $arr[$y])
    {
        $rand = rand(1,100000);
        $y++;
    }
    $arr[$i] = $rand;
}

这样做的坏处就是 刚开始取得第一个数的时候进入while循环的概率是1/100000,那么当取到了第99999个数的时候,进入while循环的几率就是99.9999%,那么这时候就会出现无限循环状态,那么如何规避这个问题呢?

阅读 3.1k
评论 更新于 2016-03-18
    9 个回答
    incNick
    • 6.3k

    把10万个数放在数组里面,然后数组随机顺序就行了。好吧,我承认这么搞根本符合题意。
    下面的伪码应该是期望的,不过貌似接近 @Dappur 的答案。

    $arr=range(1, 100000, 1);
    //shuffle($arr); 哈哈,这是玩笑
    $results = [];
    for($i=99999;$i>=0;$i--)
    {
        $key=rand(0,$i);
        $results[]=$arr[$i];
        array_slice($arr, $i, 1);
    }

    shuffle: 打乱数组顺序。
    range: 创建区间数组,参数分别是最小值、最大值、步长。
    array_slice: 取出数组中的一段,并重置下标。

    重新@Dappur
    想明白你的代码了...相当于10万个人,每个人举着一个号,然后喊一声跑,自然就乱了。
    而像楼主说的那种逐个产生(就是不事先预定好)除了他自己写的那种方式外则是无解的,就像10万人都是隔离的,自由说一个数,还不能和别人重复,不可能。

    评论 赞赏 2016-03-18