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%，那么这时候就会出现无限循环状态,那么如何规避这个问题呢？
写回答
-
IT从业UPDATE:既然题主明确了题意，我这里也更新下：
生成10W个数，值域[1..10w]且无重复，那么只需要先在长度为10W的数组内填上1..10W，然后用下面的算法shuffle就行。
这个实际上可以通过Fisher-Yates shuffle算法来实现，渐进复杂度可以达到O(n)。描述如下：
void randomize(vector<int>& data) { for (int i = data.size() - 1; i > 0; --i) { int random = rand() % (i + 1); // 所以 0 <= random <= i swap(data[random], data[i]); } }要证明这个算法的正确性也很简单。但是需要将条件转换成等价的形式，条件里说我们需要对数组随机排列，这意味着每个数出现在某个位子的几率均等，均为1/n（假设有n个数）
我们考虑算法执行第一次循环的时候：我们从[0,n-1]这n个数里随机挑选了一个数放到n-1这个位置，所以所有的数放到n-1的概率为1/n
当执行第二次的时候，我们从[0...n-2]这n-1个剩下的数里选出了一个放到n-2这个位置，那么出现在n-2位置的概率是多少呢？注意现在这件事并不是独立事件了，一个数要放到n-2这里意味着它没有在第一次迭代中被选中，并且第二次被选中了，所以概率为(1-1/n)(1/(n-1)) = ((n-1)/n)(1(n-1)) = 1/n，故而所有数放在n-2的概率为1/n
一般的，一个数放在位置i时，意味着前面n-i-1次循环他都未被选中，且在第n-i次被选中，我们有概率p(i) = (1-1/n)(1-1/(n-1))(1-1/(n-2))....(1-1/(i+2))(1/(i+1) = ((n-1)/n) ((n-2)/(n-1)) ((n-3) / (n-2))...((i+1)/(n+2))(1/(i+1)) = 1/n
2019-07-17 19:20:46赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
