面试题：如何实现红包算法 |
您所在的位置：网站首页 › 群里面每个人发一个钱一样的红包怎么发 › 面试题：如何实现红包算法 |
面试题：如何实现红包算法
|
题目
例如一个人在群里发了100块钱的红包，群里有10个人一起来抢红包，每人抢到的金额随机分配。
红包功能需要满足哪些具体规则呢？
1. 所有人抢到的金额之和要等于红包金额，不能多也不能少。
2. 每个人至少抢到1分钱。
3. 要保证红包拆分的金额尽可能分布均衡，不要出现两极分化太严重的情况。
解决方案
解决方法一
思路
二倍均值法：假设剩余红包金额为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元。假设第2个人随机抢到了20元，那么剩余金额是60元。60÷3×2 = 40，所以第3个人抢到的金额的随机范围同样是[0.01，39.99]元，平均可以抢到20元。以此类推，每一次抢到金额随机范围的均值是相等的。
代码实现
package arithmetic.com.ty.binary;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class RedEnvelope {
/**
* 拆分红包
*
* @param totalAmount 总金额（以分为单位）
* @param totalPeopleNum 总人数
*/
public static List divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
List amountList = new ArrayList();
Integer restAmount = totalAmount;
Integer restPeopleNum = totalPeopleNum;
Random random = new Random();
for (int i = 0; i < totalPeopleNum - 1; i++) {
//随机范围：[1，剩余人均金额的2倍-1] 分
int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
restAmount = restAmount - amount;
restPeopleNum--;
amountList.add(amount);
}
amountList.add(restAmount);
return amountList;
}
public static void main(String[] args) {
List amountList = divideRedPackage(1000, 10);
for (Integer amount : amountList) {
System.out.println(" 抢到金额：" + new BigDecimal(amount).divide(new BigDecimal(100)));
}
}
}
缺点：这个方法虽然公平，但也存在局限性，即除最后一次外，其他每次抢到的金额都要小于剩余人均金额的2倍，并不是完全自由地随机抢红包。 解决方法二 思路 线段切割法：何谓线段切割法？我们可以把红包总金额想象成一条很长的线段，而每个人抢到的金额，则是这条主线段所拆分出的若干子线段。
当N个人一起抢红包的时候，就需要确定N-1个切割点。 因此，当N个人一起抢总金额为M的红包时，我们需要做N-1次随机运算，以此确定N-1个切割点。 随机的范围区间是（1， M）。当所有切割点确定以后，子线段的长度也随之确定。这样每个人来抢红包的时候，只需要顺次领取与子线段长度等价的红包金额即可。 这就是线段切割法的思路。在这里需要注意以下两点： (1)当随机切割点出现重复，如何处理 --- 重复了就重新切呗(2)如何尽可能降低时间复杂度和空间复杂度 --- 这里我用链表，牺牲时间换取空间（排了个序），也可以牺牲空间节省时间（大数组） 代码 package arithmetic.com.ty.binary; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.concurrent.ThreadLocalRandom; public class RedEnvelope { public static List hongbao(int totalAmount, int totalNumber) { List list = new ArrayList(); if (totalAmount |
【本文地址】
今日新闻 |
推荐新闻 |