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 个回答
    Dappur
    • 1.4k

    看到题目的第一个反应,真的只有我想到了C++的STL中的random_suffle函数么……
    后来仔细看了一下题主用的是PHP(为啥贴的是C标签啊……)
    好吧,我们来个简化版的。
    结果一看,dahakawang已经给出实现了,好吧,就由我改成PHP语法吧~

    $a=array();
    for($i=0;$i<100000;$i++) $a[$i]=$i+1;
    for($i=99999;$i>=0;$i--)
    {
        $j=rand(0,$i);
        $t=$a[$j];
        $a[$j]=$a[$i];
        $a[$i]=$t;
    }

    直接手写的,如有语法错误自行改正。

    评论 赞赏 2016-03-18