求问一道算法题

给一个m和一个n
只能用1 + Random.nextInt(m)来生产 1 ~ m的数字

要求是生产n个没有重复的数字，这些数字都要在[1, m]之间。

两个方案：
第一个方案：用一个set，每次生成完以后就放进去，下次生成的时候就检查。
第二个方案：用一个list,每次生成完以后就把它给扔出去，再从里面生成剩下的。

这两个方案都不好，第一个是在m,n都很大的时候，执行的次数多。
第二个方案是如果m很大的时候空间会比较大。

有没有更好的方案呢？

这就是标准的reservoir sampling问题，你只需O(n)内存保存最后生成的结果即可。见
https://en.wikipedia.org/wiki/Reservoir_sampling

stellari 发表于 2018-12-5 12:38
这就是标准的reservoir sampling问题，你只需O(n)内存保存最后生成的结果即可。见
https://en.wikipedia.o ...

嗯，我大概了解了。谢谢。

stellari 发表于 2018-12-5 12:38
这就是标准的reservoir sampling问题，你只需O(n)内存保存最后生成的结果即可。见
https://en.wikipedia.o ...

主要我当时提出了蓄水池算法，他不是很满意。然后说让我自己实现data structure, 说是用树，我表示很懵逼啊。。不知道层主有没有什么想法。

更好的方案不知道.. 不过一个参考信息是统计/DS常用的R语言中的"sample"函数以及Python的Numpy包中的"random.choice"都是用的你所说的两个方案

R语言的sample函数的顶层定义（一小段dispatch代码，根据m、n的大小选择具体底层调用）：https://github.com/wch/r-source/blob/5a156a0865362bb8381dcd69ac335f5174a4f60c/src/library/base/R/sample.R#L30
其在m > 10^7 且 n <= m/2时会使用方案一：https://github.com/wch/r-source/blob/d8279508eb30d9ce61c75f45190901f2a4d77be5/src/main/unique.c
否则使用方案二：https://github.com/wch/r-source/blob/9cdb15a838bc7bec0a26b3abf312ab842a85b509/src/main/random.c#L535

Numpy包里的实现更暴力一些，直接做一个permutation（相当于方案二）然后取数组前n个值：https://github.com/numpy/numpy/blob/7c41164f5340dc998ea1c04d2061f7d246894955/numpy/random/mtrand/mtrand.pyx#L1189


补充内容 (2018-12-6 14:11):
R语言中方案一的链接没有带上行号，应该是：
https://github.com/wch/r-source/ ... main/unique.c#L1821

Similar to LC 710.

O(n) time