V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
abc0def
V2EX  ›  程序员

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

  •  
  •   abc0def · 128 天前 · 3671 次点击
    这是一个创建于 128 天前的主题,其中的信息可能已经有所发展或是发生改变。

    电话面试被问了一个很有趣的问题:给一个函数 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
    liuhuan475
        1
    liuhuan475  
       128 天前
    n 是固定的?还是每次都传不一样的?
    brazz
        2
    brazz  
       128 天前   ❤️ 1
    如果共享内存,为什么不能先打乱排好顺序,后续需要几个数,弹几个数出来
    opengps
        3
    opengps  
       128 天前
    乱序之后按顺序取用就行了
    liuhuan475
        4
    liuhuan475  
       128 天前
    想到一个解法,用 set 存返回过的数字,生成一个 0-n 的 linkedlist ,生成的时候判断有没有在 set 出现过,出现过则跳过,生成完用 Collections.shuffle()随机打乱一下这个 linkedlist ,然后 remove 前 m 个数字,把这 m 个数字存到 set 里面,并把 m 当作结果返回。时间复杂度 O(n),空间复杂度 O(n)
    iOCZS
        5
    iOCZS  
       128 天前
    对 n,n-1...的下标进行随机抽取,这样能保证每次都能取到数
    abc0def
        6
    abc0def  
    OP
       128 天前 via iPhone
    @brazz 没有提供打乱顺序的功能
    abc0def
        7
    abc0def  
    OP
       128 天前 via iPhone
    @iOCZS 对,但需要每次把选到的放到最后不然会重复选
    abc0def
        8
    abc0def  
    OP
       128 天前 via iPhone
    @opengps 没有提供乱序的接口
    fov6363
        9
    fov6363  
       128 天前
    将 array shuffle 后,维护一个 readIndex ,每次取 [readIndex, readIndex + m], 然后 readIndex = readIndex + m 。如果 readIndex > array.length ,返回 null 结束
    abc0def
        10
    abc0def  
    OP
       128 天前 via iPhone
    @liuhuan475 这个问题主要难点是没有提供乱序接口,只有一个函数返回 0 ,n 的一个随机数
    EchoWhale
        11
    EchoWhale  
       128 天前
    不提供接口, 自己实现乱序不就行了?
    cccccccccccccccd
        12
    cccccccccccccccd  
       128 天前   ❤️ 2
    i = rand(n)
    返回 a[i], a[i] = a[n-1]
    n -= 1
    EchoWhale
        13
    EchoWhale  
       128 天前   ❤️ 2
    其实他的本意就是让你用 getRandom 实现自己的乱序函数吧?

    每次调用 getRandom, 拿到一个 idx, 放到数组末尾, 数组长度--
    Maboroshii
        15
    Maboroshii  
       128 天前
    先随机一个数 k, 然后递归 [0, k), [k+1, n) 范围随机下一个 k
    abc0def
        16
    abc0def  
    OP
       128 天前 via iPhone
    @EchoWhale 对 我感觉是这个意思
    wuyadaxian
        17
    wuyadaxian  
       128 天前
    面试的话就要猜猜面试官的意图。
    大概率是实现自己的乱序函数。

    实际工作中会有几个问题。
    1 、getRandom(x) 返回的数是个有限集合吗?有没有可能返回的数的集合非常大或者无限。
    2 、此项工作中更注重时间还是空间?
    3 、能跑就行。
    ppddtt
        18
    ppddtt  
       128 天前
    既然不能乱序数据,你可以乱序索引,shuffle(n), 取前 m 个,然后从 m 个索引里面取
    wuyadaxian
        19
    wuyadaxian  
       128 天前
    补充一点,还有就是 getRandom(x) 的返回值有可能分布并不是平均分布,比如是正态分布。
    而获取正态分布两端极小概率的值本来就需要很长的运行周期,
    中间部分的值会经常重复出现。

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

    所以实际工作下,代码能跑就行。
    Sawyerhou
        20
    Sawyerhou  
       128 天前
    考虑类似#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
    pkoukk
        22
    pkoukk  
       128 天前
    getRandom 本身并不能保证不返回重复的数吧?
    那 RandomNumberGenerator 里肯定就要包含一个 Set 啊
    初始化的时候持续调用 getRandom 获取 n 个不重复的随机数
    然后 generate() 顺序返回就可以了吧
    liuhuan475
        23
    liuhuan475  
       128 天前
    @abc0def 自己打乱一下也不难
    baislsl
        24
    baislsl  
       128 天前
    array shuffle 的算法
    https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

    按照'opposite direction'实现, 每次循环返回 a[i]
    poorLi
        25
    poorLi  
       128 天前
    洗牌算法了解下
    forty
        26
    forty  
       128 天前
    思路 1:通用的线性同余伪随机数生成算法,在 1 个周期内不会重复,编程语言里自带的随机数发生器一般都是它。你只要记住每次的种子就行了,保证你在用完每个数之前都不会重复。这个算法甚至都不需要用到题目提供的函数 getRandom(x) 。

    思路 2:先用洗牌算法打乱,然后挨个取,保证不重复。但不适合数量太大的情况。比如从 2^32 个数里面随机取 2^16 个数 ,就没那么大的内存了,此时要用思路 1 更合适。
    Lhcfl
        27
    Lhcfl  
       128 天前
    很好写啊,用一个伪的数组。已知 array shuffle 是每次将 a[i] 与 a[i ~ n] 中的某个元素交换。你把这个过程 lazy 一下,每次 generate 就输出 (mapped[i] || i) swap (getRandom(n-i) + i),这样每次操作都是 O(1)的,空间也是复杂度也很优秀。
    wuyadaxian
        28
    wuyadaxian  
       128 天前
    又重新思考了下,楼主说的 [最简单的解法] 才是最好的解法。
    如果担心死循环,做一个时间上的限制即可,超出时间就抛出错误,或者返回-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 次即可。
    -------------------------------------
    接下来下一个版本要实现 [全卡池不重复十连抽] (不掉落重复卡牌)功能。
    该你设计了。
    sunrealzhang
        29
    sunrealzhang  
       128 天前
    就每次用 random 函数来根据数组可用元素长度随机取一个下标来找到元素,完了把它和数组最后一个空闲下标元素替换,这时数组可用元素长度-1 ,然后再用 random 函数以此类推着来,取够为止
    YsHaNg
        30
    YsHaNg  
       128 天前
    @abc0def 没提供人也没阻止你自己写呀 jd 没说招调包侠吧
    ZZ74
        31
    ZZ74  
       128 天前
    参考 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 获取定位访问的子数组下标。
    如果已经使用过了,或者全部都使用了,这种边界反正大家都懂的。
    Knuth
        32
    Knuth  
       128 天前 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;
    }
    Knuth
        33
    Knuth  
       128 天前 via iPhone   ❤️ 1
    @Knuth 这个算法是 knuth 大佬提出的(
    starwing
        34
    starwing  
       128 天前
    @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
    }

    ```
    leonshaw
        35
    leonshaw  
       128 天前
    @Knuth 不太一样,首先,一次调用时 m 是否已知?其次,概率分布是否与次序相关?例如第一次取到 100 的概率是 0.
    weiwoxinyou
        36
    weiwoxinyou  
       128 天前
    如果只是想要一个伪随机的数,我感觉可以直接用计算机标准时间来实现:
    1. 获取 n 的位数 x
    2. 获取当前毫秒数
    3. 获取当前毫秒数最后 x 位, 转化为整数 y
    3. 判断 y 是否在 set, 不在则直接返回,否则重复 1-3
    时间复杂度为 O(1), 空间复杂度为 O(m)
    Knuth
        38
    Knuth  
       128 天前 via iPhone
    @leonshaw 概率分布和次序无关,只是用数学归纳法证明等概率,至于 m 你看原贴内容
    lindt99cocoa
        39
    lindt99cocoa  
       128 天前
    @Knuth 这么多回复里只有这个是正确的,这个题的难点不是提出算法,而是给出证明
    paopjian
        40
    paopjian  
       128 天前
    @Knuth 你这名字我以为是你提出来的,吓一跳
    mingl0280
        41
    mingl0280  
       128 天前 via Android
    随便猜的:
    声明一个数组 result ,长度 m 。
    从 n 中弹一个
    mingl0280
        42
    mingl0280  
       128 天前 via Android
    ……别人写过了,就是直接写个乱序数组一个一个弹就行了
    leonshaw
        43
    leonshaw  
       128 天前 via Android
    @Knuth 这个算法结果是递增的,要跟次序无关还需要做一次打乱。关于 m 的问题,可能讨论有一些偏差,我指的是原题,而 op “从 n 个数里面随机取 m 个数” 的表述已经和原题不等价。
    fpk5
        44
    fpk5  
       128 天前
    读第 i 个数就把 arr[i]跟 arr[i+random(n - i)]交换并输出这个数,i++。无额外空间,时间复杂度取决于 random 。

    这个叫 fisher-yates 算法 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
    nativeBoy
        45
    nativeBoy  
       127 天前
    写个数组,然后取走的数字就设置为-1 ,如果发现已经取了,就用算法寻找下一个位置(类似于哈希开放寻址法)
    Sawyerhou
        46
    Sawyerhou  
       127 天前
    看来看去,似乎还是 op 的解法相对更优。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   997 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 21:37 · PVG 05:37 · LAX 13:37 · JFK 16:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.