一 背景
最近在整理过去的项目时，回顾了某年红包活动的项目，其中涉及红包金额计算的算法。近些年各家大厂举办的春节红包活动越来越完善，关于活动背后的整体设计介绍、分析、探讨层出不穷。本篇先不关注整体架构，选择红包金额的计算方法作为分析内容。
在当时的项目中，红包金额计算主要是采用了基于一些入参的随机数生成，并且生成的是单个红包金额，并未使用队列方式做预生成。所以再次回顾这个案例，其中其实还有很多可以玩味和深入思考的地方，在这里做一次思考总结。
二 题目描述
要求设计在微信群抢红包的算法，红包总金额为m元，分成n份，要求返回一个红包金额数组。算法需要满足下面的几条要求：
- 前n个抢红包的人都能抢到钱，第n个之后的人直接返回空包，所以这里不做考虑；
- 每个人能抢到的红包金额是随机的，但随机范围最大化(有机会获得可能的最多金额) ；
- 抢到红包的每个人，抢到相同金额的概率是一样的。
三 传说中微信红包算法
网上其实可以搜到很多关于红包金额计算方法的解析，例如 微信红包的随机算法是怎样实现的？，给出了一个传说是微信内部人提供的代码：
public static double getRandomMoney(RedPackage _redPackage){ //remainSize 剩余的红包数量 //remainMoney 剩余的钱 if(_redPackage.remainSize == 1){ _redPackage.remainSize--; return (double) Math.round(_redPackage.remainMoney * 100)/100; } Random r = new Random(); double min = 0.01; double max = _redPackage.remainMoney / _redPackage.remainSize * 2; double money = r.nextDouble() * max; money = money <= min ? 0.01 : mondy; money = Math.floor(money * 100) / 100; _redPackage.remainSize--; _redPackage.remainMoney -= money; return money; }
当然，double类型显然是不靠谱的，楼主也做了补充，商业计算需要使用java.math.BigDecimal；并且在回答中提供了测试结果，包括金额分布情况。
四 一个朴素且简单的思考实现
4.1 分析
如果我们自己从头思考，那么会考虑怎样来实现呢？一个简单的方法，n个人，生成n次金额数据，当然，我们也要保证n次的金额综合=m元，且每次每人领取到的金额最小值是0.01元，也就是一分钱；最大值是当前的剩余金额-剩余人数。例如总金额1元，5个人可抢，那么第一个人可以抽到的最大金额是0.96元，之后每个人领取一元，这是最极端的情况。
其次，上面的这种算法是否能够保证绝对随机？如果不能，那么我们是否有修正策略来做个补救？争取让每个人可能获得的金额尽可能的达到随机效果？
当然，如果能从算法上直接解决是最好的。但如果短时间想不到能够最为符合要求的算法，那么就只能考虑这种补救方法，虽然效率上要差一些，但可以符合要求。既然生成的金额数组可能不是绝对平均，那么我们再生成一次随机数组，调整初始金额数组中各元素的顺序，做个随机乱序，那么就可以接近题目要求的效果。
4.2 一个代码实现（未优化）
public int[] createRandomArr(int m, int n) throws Exception{ int[] ret = new int[n]; int total = m*100; Random random = new Random(); int cur = 1; int curSum = 0; while(cur <= n-1){ int curLeft = total-curSum-(n-cur); int curAcount = random.nextInt(curLeft); curAcount = 1+curAcount; ret[cur-1] = curAcount; curSum+=curAcount; cur++; } ret[n-1] = total-curSum; int[] newRet = new int[n]; Map<Integer, Boolean> map = new HashMap<Integer, Boolean>(); for(int i=0;i<n;i++){ int index = random.nextInt(n); while(map.containsKey(index)){ index = random.nextInt(n); } newRet[i] = ret[index]; map.put(index, true); } return newRet; }
五 再次思考
容易看出，上面的算法非常粗糙，不过也勉强能达到题目的大部分要求。影响效率严重的点，就是在生成随机索引数组，也就是第22行。上面的示例代码是通过while循环来实现的。这里可以考虑通过分段优化的方式来避免while循环。事实上，如果java中有类似php中shuffle（洗牌，做数组随机乱序）的方法，那么就可以直接使用来做第二步的乱序逻辑了。更多的优化，留给大家来思考了。
