电话面试被问了一个很有趣的问题：给一个函数 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 个数 ，不知道有没有更好的解法。
46 条回复 • 2024-08-20 14:38:12 +08:00
 |
1
liuhuan475 28 天前
n 是固定的？还是每次都传不一样的？
|
 |
2
brazz 28 天前  1
如果共享内存，为什么不能先打乱排好顺序，后续需要几个数，弹几个数出来
|
 |
3
opengps 28 天前
乱序之后按顺序取用就行了
|
|
4
liuhuan475 28 天前
想到一个解法，用 set 存返回过的数字，生成一个 0-n 的 linkedlist ，生成的时候判断有没有在 set 出现过，出现过则跳过，生成完用 Collections.shuffle()随机打乱一下这个 linkedlist ，然后 remove 前 m 个数字，把这 m 个数字存到 set 里面，并把 m 当作结果返回。时间复杂度 O(n)，空间复杂度 O(n)
|
 |
5
iOCZS 28 天前
对 n,n-1...的下标进行随机抽取，这样能保证每次都能取到数
|
 |
9
fov6363 28 天前
将 array shuffle 后，维护一个 readIndex ，每次取 [readIndex, readIndex + m], 然后 readIndex = readIndex + m 。如果 readIndex > array.length ，返回 null 结束
|
 |
10
abc0def OP @liuhuan475 这个问题主要难点是没有提供乱序接口，只有一个函数返回 0 ，n 的一个随机数
|
 |
11
EchoWhale 28 天前
不提供接口, 自己实现乱序不就行了?
|
 |
12
cccccccccccccccd 28 天前 2
i = rand(n)
返回 a[i], a[i] = a[n-1] n -= 1 |
|
13
EchoWhale 28 天前 2
其实他的本意就是让你用 getRandom 实现自己的乱序函数吧?
每次调用 getRandom, 拿到一个 idx, 放到数组末尾, 数组长度-- |
 |
15
Maboroshii 28 天前
先随机一个数 k, 然后递归 [0, k), [k+1, n) 范围随机下一个 k
|
 |
17
wuyadaxian 28 天前
面试的话就要猜猜面试官的意图。
大概率是实现自己的乱序函数。 实际工作中会有几个问题。 1 、getRandom(x) 返回的数是个有限集合吗？有没有可能返回的数的集合非常大或者无限。 2 、此项工作中更注重时间还是空间？ 3 、能跑就行。 |
 |
18
ppddtt 28 天前
既然不能乱序数据，你可以乱序索引，shuffle(n), 取前 m 个，然后从 m 个索引里面取
|
|
19
wuyadaxian 28 天前
补充一点，还有就是 getRandom(x) 的返回值有可能分布并不是平均分布，比如是正态分布。
而获取正态分布两端极小概率的值本来就需要很长的运行周期， 中间部分的值会经常重复出现。 在不能查看 getRandom(x) 源代码的情况下，如果你又不知道 getRandom(x) 返回的值的集合是不是一个有限集合。 可能会陷入时间和空间都无法预测的情况。 所以实际工作下，代码能跑就行。 |
 |
20
Sawyerhou 28 天前
考虑类似#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 |
 |
21
meilicat 28 天前
|
 |
22
pkoukk 28 天前
getRandom 本身并不能保证不返回重复的数吧？
那 RandomNumberGenerator 里肯定就要包含一个 Set 啊 初始化的时候持续调用 getRandom 获取 n 个不重复的随机数 然后 generate() 顺序返回就可以了吧 |
|
23
liuhuan475 28 天前
@abc0def 自己打乱一下也不难
|
 |
24
baislsl 28 天前
array shuffle 的算法
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle 按照'opposite direction'实现, 每次循环返回 a[i] |
 |
25
poorLi 28 天前
洗牌算法了解下
|
 |
26
forty 28 天前
思路 1：通用的线性同余伪随机数生成算法，在 1 个周期内不会重复，编程语言里自带的随机数发生器一般都是它。你只要记住每次的种子就行了，保证你在用完每个数之前都不会重复。这个算法甚至都不需要用到题目提供的函数 getRandom(x) 。
思路 2：先用洗牌算法打乱，然后挨个取，保证不重复。但不适合数量太大的情况。比如从 2^32 个数里面随机取 2^16 个数 ，就没那么大的内存了，此时要用思路 1 更合适。 |
 |
27
Lhcfl 28 天前
很好写啊，用一个伪的数组。已知 array shuffle 是每次将 a[i] 与 a[i ~ n] 中的某个元素交换。你把这个过程 lazy 一下，每次 generate 就输出 (mapped[i] || i) swap (getRandom(n-i) + i)，这样每次操作都是 O(1)的，空间也是复杂度也很优秀。
|
|
28
wuyadaxian 28 天前
又重新思考了下，楼主说的 [最简单的解法] 才是最好的解法。
如果担心死循环，做一个时间上的限制即可，超出时间就抛出错误，或者返回-1 不存在此数，即可。（有限时间内的最好解法） 1 、这个算法不需要公开或者了解 getRandom(x) 内置算法的逻辑。 2 、这个算法基本不会改变 getRandom(x) 内置的概率。 3 、这个算法不需要关心 getRandom(x) 返回的所有值的集合有多大，集合是否包含 0 到 x-1 的所有整数，是有限集合还是无限集合。 4 、这个算法容易让人理解。容易移交。 ================================= 让我们设想一个场景： 一家手游公司，做了抽卡系统。 卡池就是 list(n)，list 里面每个下标对应一张卡。 公司设计了一个复杂的抽卡系统。 卡牌里面有 SSR ，SR ，R ，N 等不同卡牌，对应不同权重概率。 调用方法就是 getRandom(n) ，然后会按照设定好的权重概率返回一个卡牌给用户。（全卡池单抽） ------------------------------------- 新上线的时候，卡池只有 10 张卡。 所以 getRandom(9)，大家开心抽卡。 ------------------------------------- 1 个月后，版本更新。 卡池有 20 张卡了。 大家就变成了 getRandom(19)，开心抽卡。 ------------------------------------- 又过了半个月，画师 W 被爆出美术抄袭，第 14 号卡牌被迫删除下架。 程序大佬将 getRandom(n)内部权重概率调整了下。 外部调用还是 getRandom(19)。但是已经抽不到 list(13)卡牌了，因为权重变为 0 了。 大家开心继续运营。 ------------------------------------- 又过了 1 个月，版本更新。加了 10 张卡，外加增加了 10 连抽功能。（全卡池十连抽） getRandom(29)，继续用起来。 10 连抽？调用 10 次即可。 ------------------------------------- 接下来下一个版本要实现 [全卡池不重复十连抽] （不掉落重复卡牌）功能。 该你设计了。 |
 |
29
sunrealzhang 28 天前
就每次用 random 函数来根据数组可用元素长度随机取一个下标来找到元素，完了把它和数组最后一个空闲下标元素替换，这时数组可用元素长度-1 ，然后再用 random 函数以此类推着来，取够为止
|
 |
31
ZZ74 28 天前
参考 Java HashMap 的做法 数组+数组
比如 [0 ，101 ）的数组 Arr 分成 5 份，每份数组长度 20 ，Arr_x[i]存是否已经用过。下标 i 是返回的随机数，用长度为的 5 数组 KeyArr 分别对应这个 5 份数组，KeyArr[i]=Arr_x 。 取值的时候采用 hash 算法定位长度为 5 的数组的下标，然后、 1.每一份都有 lastUsedIndex 用 lastUsedIndex+1 来获取。 或者 2.使用 hash 获取定位访问的子数组下标。 如果已经使用过了，或者全部都使用了，这种边界反正大家都懂的。 |
 |
32
Knuth 28 天前 via iPhone
很经典的面试题，很经典的算法
附上代码 #include <cstddef> #include <cstdlib> #include <iostream> // 等概率无重复的从 N 个数挑出 M 个数, 输出范围是 0~N-1 ，M < N using namespace std; // 1. 无重复 m 个值：i 不同保证无重复，m--控制个数 // 2. 等概率： // i = 0 时，输出 i 只需 rand() % (n - i) < m,概率=m/n // i = 1 时，输出 i 有两种情况，0 输出还是没输出，0 输出：m-1/n-1, 0 没输出：m/n-1,综合两者可得(m/n)*(m-1/n-1) + (1-m/n)*(m/n-1)=m/n void genknuth(int m, int n) { for (int i = 0; i < n; i++) { if (rand() % (n - i) < m) { cout << i << endl; m--; } } } int main() { int m = 8, n = 100; genknuth(m, n); return 0; } |
 |
34
starwing 28 天前
@Knuth 这个算法很优秀，但它是 O(n)级别的，如果 n 很大但是 m 很小会很慢。我以前搞出一个“模拟打乱算法”是 O(m)级别的，原理是模仿打乱算法，但是不真的做一个 O(n)的数组出来，而是用 hash 表代替“已经打乱过的区域”，只需要 O(m)的空间即可。在 m 很小但是 n 很大的时候会比较优，下面是 Go 的实现：
```golang // SampleFilter 随机采样[0-N)中的 m 个，排除 f 返回 false 的元素. func SampleFilter(n uint32, m uint32, f func(uint32) bool) []uint32 { if n == 0 || m == 0 { return nil } // 如果采样结果比长度还多，就直接顺序返回全部值 if m >= n { indexes := make([]uint32, 0, n) for i := uint32(0); i < n; i++ { if f(i) { indexes = append(indexes, i) } } return indexes } // 否则，做一个虚拟索引映射表（表里不存在的就是原索引），走洗牌算法 indexMap := make(map[uint32]uint32, m) indexes := make([]uint32, 0, m) for i := uint32(0); i < n; i++ { if uint32(len(indexes)) >= m { return indexes } // 先获取一个随机索引的映射 ri := RangeRand(i, n-1) mappedIdx, ok := indexMap[ri] if !ok { mappedIdx = ri } // 如果满足要求，就加入到结果中 if f(mappedIdx) { indexes = append(indexes, mappedIdx) } // 在随机位置填入当前位置映射后的索引 indexMap[ri], ok = indexMap[i] if !ok { indexMap[ri] = i } } return indexes } ``` |
 |
36
weiwoxinyou 28 天前
如果只是想要一个伪随机的数，我感觉可以直接用计算机标准时间来实现：
1. 获取 n 的位数 x 2. 获取当前毫秒数 3. 获取当前毫秒数最后 x 位, 转化为整数 y 3. 判断 y 是否在 set, 不在则直接返回，否则重复 1-3 时间复杂度为 O(1), 空间复杂度为 O(m) |
 |
39
lindt99cocoa 28 天前
@Knuth 这么多回复里只有这个是正确的，这个题的难点不是提出算法，而是给出证明
|
 |
41
mingl0280 28 天前 via Android
随便猜的：
声明一个数组 result ，长度 m 。 从 n 中弹一个 |
|
42
mingl0280 28 天前 via Android
……别人写过了，就是直接写个乱序数组一个一个弹就行了
|
 |
43
leonshaw 28 天前 via Android
@Knuth 这个算法结果是递增的，要跟次序无关还需要做一次打乱。关于 m 的问题，可能讨论有一些偏差，我指的是原题，而 op “从 n 个数里面随机取 m 个数” 的表述已经和原题不等价。
|
 |
44
fpk5 28 天前
读第 i 个数就把 arr[i]跟 arr[i+random(n - i)]交换并输出这个数，i++。无额外空间，时间复杂度取决于 random 。
这个叫 fisher-yates 算法 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle |
 |
45
nativeBoy 27 天前
写个数组，然后取走的数字就设置为-1 ，如果发现已经取了，就用算法寻找下一个位置（类似于哈希开放寻址法）
|
|
46
Sawyerhou 27 天前
看来看去，似乎还是 op 的解法相对更优。
|
Select Language