爱奇艺面试小记

今天参加了一次爱奇艺的面试，在面试中被问道一道算法相关的题目：按照指定的权重求随机数

按照指定的权重求随机数

描述：通常取随机数，取到每个数字的概率都是一样，比如取 n 次，取到某个数的概率都是 1/n。现在情况发生了变化，要随机取的数，每个数字都被设置了一个权值（weight），比如：

上面这个图表的含义是：进行随机取数，取到 1 的概率是 1/5，取到 2 概率是 2/5，取到 3 的概率是 2/5。现在要求你使用代码完成这个按照不同权值进行取值的过程。

一开始想到方法是：

使用一个数组 value ，数组的下标对应于这个权重的范围，下标对应的值就是要求的值，比如还是上面这个例子，比如在 1 < x <= 3这个区间范围内，然后对整个区间长度求随机值，rand(1, 5) 会得到一个下标值，然后根据这个下标值去获取想要的值。这个解法的问题是，如果某个值的权值很大，那么需要一个很大的数组，这样会非常非常消耗内存，显然不是一个很好的解决方法。不过当时也没有想到更好的方法。

晚上回来想了想，有没有可以优化的方向

p(x = 1) = 1/5  (x <= 1)
p(x = 2) = 2/5  (1 < x <= 3)
p(x = 3) = 2/5  (3 < x <= 5)

转换成累积概率：

cp(x = 1) = 1/5 (x <= 1)
cp(x = 2) = 3/5 (1 < x <= 3)
cp(x = 3) = 1 (3 < x <= 5)

有上面这个映射关键，在 0 - 1 随机取一个数 x，如果 x <= cp[i] ，i 就是所要求的结果：

Python 实现

import random

def random_by_weight(values, cp):
    for v, w in zip(values, cp):
        rand = random.randint(0, 1)
        if  rand <= w:
             return v