从 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 个数 ，不知道有没有更好的解法。

[liuhuan475]

n 是固定的？还是每次都传不一样的？

[brazz]

如果共享内存，为什么不能先打乱排好顺序，后续需要几个数，弹几个数出来

[opengps]

乱序之后按顺序取用就行了

[liuhuan475]

想到一个解法，用 set 存返回过的数字，生成一个 0-n 的 linkedlist ，生成的时候判断有没有在 set 出现过，出现过则跳过，生成完用 Collections.shuffle()随机打乱一下这个 linkedlist ，然后 remove 前 m 个数字，把这 m 个数字存到 set 里面，并把 m 当作结果返回。时间复杂度 O(n)，空间复杂度 O(n)

[iOCZS]

对 n,n-1...的下标进行随机抽取，这样能保证每次都能取到数

[abc0def]

@brazz 没有提供打乱顺序的功能

[abc0def]

@iOCZS 对，但需要每次把选到的放到最后不然会重复选

[abc0def]

@opengps 没有提供乱序的接口

[fov6363]

将 array shuffle 后，维护一个 readIndex ，每次取 [readIndex, readIndex + m], 然后 readIndex = readIndex + m 。如果 readIndex > array.length ，返回 null 结束

[abc0def]

@liuhuan475 这个问题主要难点是没有提供乱序接口，只有一个函数返回 0 ，n 的一个随机数

[EchoWhale]

不提供接口, 自己实现乱序不就行了?

[cccccccccccccccd]

i = rand(n)
返回 a[i], a[i] = a[n-1]
n -= 1

[EchoWhale]

其实他的本意就是让你用 getRandom 实现自己的乱序函数吧?

每次调用 getRandom, 拿到一个 idx, 放到数组末尾, 数组长度--

[araaaa]

https://chatgpt.com/share/d601e823-ef4f-4047-b539-b885f4d94677

[Maboroshii]

先随机一个数 k, 然后递归 [0, k), [k+1, n) 范围随机下一个 k

[abc0def]

@EchoWhale 对 我感觉是这个意思

[wuyadaxian]

面试的话就要猜猜面试官的意图。
大概率是实现自己的乱序函数。

实际工作中会有几个问题。
1 、getRandom(x) 返回的数是个有限集合吗？有没有可能返回的数的集合非常大或者无限。
2 、此项工作中更注重时间还是空间？
3 、能跑就行。

[ppddtt]

既然不能乱序数据，你可以乱序索引，shuffle(n), 取前 m 个，然后从 m 个索引里面取

[wuyadaxian]

补充一点，还有就是 getRandom(x) 的返回值有可能分布并不是平均分布，比如是正态分布。
而获取正态分布两端极小概率的值本来就需要很长的运行周期，
中间部分的值会经常重复出现。

在不能查看 getRandom(x) 源代码的情况下，如果你又不知道 getRandom(x) 返回的值的集合是不是一个有限集合。
可能会陷入时间和空间都无法预测的情况。

所以实际工作下，代码能跑就行。

[Sawyerhou]

考虑类似#15 的思路呢？

取第 1 个数
a_0 = getRandom(n)

取第 2 个数
a_1 = (a_0 + 1 + getRandom(n-1)) % n

取第 k 个数，
之前已经取了 k-1 个数，
其将(0, n]分为至多 k-1 个区间，
相邻的数合并为一个切割数集合，
不计入区间个数，

这里假设 j 个区间，
记 j 个切割数集合为 a_0, ..., a_{j-1}

取下一个数
i = getRandom(j)
next = (a_i_max + 1 + getRandom(a_{(i+1)%j}_min - a_i_max - 1)) % n