面试必看！抢红包随机算法设计方案

今天来聊聊面试里常考的一个场景题——设计一个抢红包随机算法。这题要是在面试里碰上了，可别慌，看完这篇，稳稳拿捏！

一、面试官出题：设计抢红包随机算法

想象一下，面试的时候，面试官突然来一句：“咱来写个算法题吧，设计一个抢红包的随机算法。比如说，有人在群里发了100块钱的红包，群里有10个人抢，每个人抢到的金额得随机分配。这里有几个要求：第一，所有人抢到的金额加起来必须正好是红包金额，一分都不能差；第二，每个人最少得抢到1分钱；第三，最佳手气的人抢到的金额不能超过红包总金额的90%。” 碰到这种题，该咋整呢？别着急，下面咱就一步步拆解。

二、解题思路1：随机分配法

（一）思路解析

这个方法其实挺好理解的。首先把钱的单位从元转换成分，为啥呢？主要是为了避免浮点误差，搞开发的都懂，浮点运算要是不注意，很容易出问题。转换完之后，每次就在[1, leaveMoney]这个区间里随机选一个值，就叫它r。这里的leaveMoney就是剩余的钱数。选完r之后，得算一下剩余金额leaveMoney – r ，而且剩余金额必须得大于剩余人数，不然后面的人就没办法分配了。比如说10个人抢红包，有1个人抢了之后，剩下的钱至少得够9个人每人分1分钱，不然就分不下去了。按照这个方法，随机选n – 1次（n是总人数），最后剩下的钱直接作为最后一个红包的金额，就不用再随机选了。

（二）代码实现

public static List<Double> generate(double totalMoney, int people) { // 转换为分处理避免浮点误差 double totalCents = Math.round(totalMoney * 100); double maxLimit = (totalCents * 0.9); // 总金额的90% double leaveMoney = totalCents; List<Double> result = new ArrayList<>(); //判断钱不够分,不处理 if ((int)totalCents < people) { return result; } Random random = new Random(); //每次生成随机数 int n = people - 1; while (n > 0) { //随机数在[1, min(maxLimit, leaveMoney)]之间，单位是:分 double min = Math.min(leaveMoney, maxLimit); double allocResult = 1 + random.nextInt((int)min); //判断这次分配后，后续的总金额仍然可分，且不超过90%总金额 if (allocResult > maxLimit || (leaveMoney - allocResult) < n) { continue; } leaveMoney -= allocResult; n--; result.add(allocResult / 100.0); } result.add(leaveMoney / 100.0); return result; }

（三）运行结果示例

多次运行这段代码，得到的结果大概是这样：

[37.77, 50.76, 1.89, 7.89, 0.26, 0.24, 0.25, 0.78, 0.06, 0.1] [89.38, 2.45, 3.5, 4.43, 0.03, 0.08, 0.06, 0.04, 0.01, 0.02] [53.51, 40.86, 5.48, 0.04, 0.06, 0.01, 0.01, 0.01, 0.01, 0.01] [42.71, 0.27, 38.99, 4.5, 4.02, 4.58, 2.97, 0.84, 0.21, 0.91]

不过，从这些结果能看出来一个问题，就是越早抢红包的人，好像抢到的金额越大。这要是真在群里抢红包，不得被人吐槽不公平？所以，面试官可能会接着“发难”，要求改进算法，让红包金额分布更均衡。

三、解题思路2：二倍均值法

（一）思路解析

为了解决上面随机分配法的问题，就有了二倍均值法。这个方法是这么个逻辑：假设剩余红包金额是m元，剩余人数是n，那么每次抢到的金额就在随机区间[0.01，m / n × 2 – 0.01]元里选。这么做有啥好处呢？它保证了每次随机金额的平均值是相等的，也就是说，不管你是先抢还是后抢，从概率上来说，大家平均能抢到的金额是一样的，不会因为抢红包的先后顺序而造成不公平。

举个例子，假设有5个人抢100元的红包。100÷5×2 = 40，所以第1个人抢到的金额随机范围就是[0.01，39.99]元，正常情况下，平均能抢到20元。要是第1个人随机抢到了20元，那剩下80元。80÷4×2 = 40，第2个人抢到的金额随机范围还是[0.01，39.99]元，平均也能抢到20元。就这么依次类推，每一次抢到金额随机范围的均值都是相等的。

（二）代码实现

public static List<Double> allocateRedEnvelop(double totalMoney, int people) { // 转换为分处理避免浮点误差 double totalCents = Math.round(totalMoney * 100); double maxLimit = (totalCents * 0.9); // 总金额的90% Random random = new Random(); double leaveMoney = totalCents; List<Double> result = new ArrayList<>(); int n = people; //注意是大于1，最后1个人领取剩余的钱 while (n > 1) { //生成随机金额的范围是[1, leaveMoney / n * 2 - 1]， 注意nextInt方法生成结果范围是左闭右开的 double allocatMoney = 1 + random.nextInt((int)leaveMoney / n * 2 - 1); result.add(allocatMoney / 100.0); n--; leaveMoney -= allocatMoney; } result.add(leaveMoney / 100.0); return result; }

（三）运行结果示例

用这个算法跑几次，得到的结果像下面这样：

[8.58, 4.56, 20.88, 13.83, 7.6, 3.94, 10.87, 8.66, 20.92, 0.16] [3.31, 2.08, 15.99, 16.79, 13.13, 0.61, 17.38, 10.93, 4.93, 14.85] [0.24, 21.86, 15.57, 16.86, 3.45, 3.18, 5.48, 13.01, 6.76, 13.59]

可以看到，这些结果比之前随机分配法的结果要随机多了，领取红包的金额和先后顺序关系不大，基本达到了分布均衡的要求。

四、解题思路3：线段切割法

（一）思路解析

还有一种挺有意思的解法，叫线段切割法。咱们把红包总金额想象成一条长长的线段，每个人抢到的金额就是这条线段上的一小段。比如说有N个人抢红包，红包总金额是M，那就得确定N – 1个切割点。这些切割点的随机范围是（1，M），等切割点都确定好了，每个子线段的长度也就确定了，这长度就是每个人抢到的金额。要是随机生成的切割点有重复的，那就重新生成。

（二）代码实现

/** * 线段切割法 */ public static List<Double> allocateRedEnvelopNew(double totalMoney, int people) { // 转换为分处理避免浮点误差 double totalCents = Math.round(totalMoney * 100); double maxLimit = (totalCents * 0.9); // 总金额的90% Random random = new Random(); double leaveMoney = totalCents; List<Double> result = new ArrayList<>(); Set<Integer> pointCutSet = new HashSet<>(); int n = people; while (pointCutSet.size() < people - 1) { //生成n - 1个切割点，随机点取值范围是[1, totalCents] pointCutSet.add(random.nextInt((int) totalCents) + 1); } //接着生成对应子线段的钱数 Integer[] points = pointCutSet.toArray(new Integer[0]); Arrays.sort(points); result.add(points[0] / 100.0); //子线段+ 最后那段的长度 = totalCents，注意上一步是已经加了points[0]，result中的所有元素和累加后的结果一定是totalCents, for (int i = 1; i < points.length; i++) { result.add((points[i] - points[i - 1]) / 100.0); } result.add((totalCents - points[points.length - 1]) / 100.0); return result; }

（三）运行结果示例

跑几次这个算法，看看结果：

[20.24, 3.9, 7.63, 9.62, 15.41, 2.32, 0.21, 24.94, 9.66, 6.07] [8.64, 33.55, 3.76, 15.35, 4.41, 9.85, 4.81, 15.9, 2.71, 1.02] [11.31, 13.32, 16.53, 5.91, 8.69, 17.29, 11.09, 7.62, 7.14, 1.1] [21.34, 8.24, 1.9, 7.98, 0.49, 0.32, 13.75, 37.27, 0.03, 8.68]

从结果能看出来，用这个方法，手气最佳的人抢到的金额可能会更高。和二倍均值法比起来，各有特点。