沐小晨曦 | Omooo

抢红包算法，了解一下？

问题描述

emmmm，就是我们平常的抢红包金额分配问题。按照正常的思路，就是每次抢到的金额为随机区间（0，剩余金额）。但是问题也很明显，这样先抢的人就会有很大的优势，越到后面区间就越小，那么怎么保证每个人抢到的金额几率相等呢？

二倍均值法

即每次抢到的金额为区间：（0，平均值x2），例如：

假设10个人抢100元

第一个人抢到的金额随机区间为：(0,100/10*2) –> (0,20) 均值为10

假设第一个人抢到10元，那么第二个人抢到的随机区间为：(0,90/9*2) –> (0,20) 均值为10

这样也就保证了每个人抢到的金额均值一致。

private static List<Integer> divider(int totalMoney, int totalPeople) {
    List<Integer> amountList = new ArrayList<>();
    int restMoney = totalMoney;
    int restPeople = totalPeople;
    Random random = new Random();
    for (int i = 0; i < totalPeople - 1; i++) {
        int amount = random.nextInt(restMoney / restPeople * 2) + 1;
        restMoney -= amount;
        restPeople--;
        amountList.add(amount);
    }
    amountList.add(restMoney);
    return amountList;
}

实现起来也并不是很难。

想法来源于@小灰

漫画：如何实现抢红包算法？

但是你仔细阅读文章的话，还是能注意到一个地方是有问题的。那就是“除了最后一次，任何一次抢到的金额都要小于人均金额的两倍”。

事实上并不是如此，因为如果第一个人抢到的值不是10，而是5，就会导致第二人抢到的均值大于10。

我们再看看知乎对这个问题的一个高票讨论，

微信红包的随机算法是怎样实现的？

实现也是差不多的，还有就是有人说到抢到的金额应该是服从正态分布的，大多数人抢到的值应该在均值附近。

关于架构方面可以看上面一篇文章。

看来一个小问题仔细思考还是有点东西的。

2018-04-23