10万个数字无序排列,要求不重复-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

10万个数字无序排列,要求不重复

2016-05-30 17:06:23 2209 1

(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%,那么这时候就会出现无限循环状态,那么如何规避这个问题呢?

取消 提交回答
全部回答(1)
  • 杨冬芳
    2019-07-17 19:20:46

    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

    0 0
相关问答

1

回答

数字金融中b端和c端是什么意思?

2022-03-30 15:11:43 925浏览量 回答数 1

0

回答

C++合并排序检查,查看列表中是否有数字

2019-12-09 09:51:49 320浏览量 回答数 0

1

回答

C++合并排序检查,查看列表中是否有数字

2019-12-09 09:51:29 1163浏览量 回答数 1

1

回答

我在华北1区一台ecs下有一块100G云盘,我想从按量计费转为包月,请问怎么转换?

2019-03-18 15:40:43 495浏览量 回答数 1

1

回答

[@徐雷frank][¥20]微服务数量众多,其测试、部署、监控等都变的更加困难,阿里是怎么优化这个问题的?

2018-12-14 23:14:33 2662浏览量 回答数 1

1

回答

创建一个Spark udf函数来迭代一个字节数组并将其转换为数字

2018-12-05 14:55:07 3670浏览量 回答数 1

1

回答

cpanel创建的电子邮箱不能收发邮件

2018-08-16 10:38:42 4402浏览量 回答数 1

1

回答

用C或者C++编写RSA加密算法,要求既能加密数字,又能加密字母!!

2018-07-19 17:59:09 1968浏览量 回答数 1

1

回答

如何在ECS Windows Server通过IIS启用Gzip压缩?

2018-01-11 16:11:05 1661浏览量 回答数 1

1

回答

我的 ECS 实例经常能在 Web 日志中看到大量的恶意 IP 访问我的网站,疑有刷流量和恶意访问的嫌疑,询问云盾是否有屏蔽 IP 的功能?

2017-12-12 16:43:51 4865浏览量 回答数 1
+关注
杨冬芳
IT从业
文章
问答
问答排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载