从 n 个数里面随机取 m 个数

[abc0def]

电话面试被问了一个很有趣的问题：给一个函数 getRandom(x) 能随机返回[0,x) 中的一个数，求实现一个 RandomNumberGenerator(n) 数据结构，里面有一个 generate() 接口，要求每次调用随机返回[0,n) 中的一个数，同时不能返回已经返回过的数。

这个题换一种说法其实就是从 n 个数里面随机取 m 个数。工作中经常遇到类似的问题，一般调用已有库函数就可以实现，所以从来没有想过这个方法的具体实现。

最简单的暴力解法，用一个 Set 来保存已经出现的数，generate() 函数不停地调用 getRandom(n)，直到生成的数字不在 set 里面，返回这个数，同时把这个数加进 Set 。这个解法最坏情况可能导致无限死循环，假设 Set 里面数字个数为 m ，那么每次成功的概率为 (n - m) / n ，如果 n 和 m 十分接近，则这个概率会很小。这个解法不被接受。

要求一个是肯定有解的算法。自己想了几个 [算法] 从 n 个数里面随机取 m 个数 ，不知道有没有更好的解法。

[mingl0280]

随便猜的：
声明一个数组 result ，长度 m 。
从 n 中弹一个

[mingl0280]

……别人写过了，就是直接写个乱序数组一个一个弹就行了

[leonshaw]

@Knuth 这个算法结果是递增的，要跟次序无关还需要做一次打乱。关于 m 的问题，可能讨论有一些偏差，我指的是原题，而 op “从 n 个数里面随机取 m 个数” 的表述已经和原题不等价。

[fpk5]

读第 i 个数就把 arr[i]跟 arr[i+random(n - i)]交换并输出这个数，i++。无额外空间，时间复杂度取决于 random 。

这个叫 fisher-yates 算法 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[nativeBoy]

写个数组，然后取走的数字就设置为-1 ，如果发现已经取了，就用算法寻找下一个位置（类似于哈希开放寻址法）

[Sawyerhou]

看来看去，似乎还是 op 的解法相对更优。