笔记

红包算法的分析与实现

张天宇 on 2020-04-14

最近在知乎看到关于抢红包分配方式的讨论，炒个冷饭，整理了一下高赞解决方案。

抢红包规则

  • 抢到红包的所有人抢到的金额之和必须等于红包金额。

  • 2.每个抢到的人至少分得一分钱。

  • 3.所有人抢到金额的概率相等。

普通思路

方法

每次拆开红包，抢到的金额=（0，剩余金额）内的随机数。

问题

以这种方式分配，即以剩下金额随机的期望作为抢到金额。先抢到的人会有很大的优势，越往后的人抢到的金额越少，不满足条件3。例如：一个10个人共100元的红包，第一个人的随机区间为（0，100），他的红包期望是50。如果他真的抢到了50，第二个人的随机区间变为（0，50），他的红包期望为25。以此类推，后面的人抢到的金额会逐渐减少。

思路一 二倍均值法

方法

假设剩余红包金额为M，剩余人数为N，每次抢到的金额 = 随机区间 （0， M / N X 2）。

这个公式，保证了每次随机金额的平均值是相等的，不会因为抢红包的先后顺序而造成不公平。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
	List<Integer> amountList = new ArrayList<Integer>();
	// 精确到小数点后两位
	Integer restAmount = totalAmount * 100;
	Integer restPeopleNum = totalPeopleNum;
	Random random = new Random();
	for (int i = 0; i < totalPeopleNum - 1; i++) {
     	// 随机范围：[1，剩余人均金额的两倍)，左闭右开
     	int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
		restAmount -= amount;
		restPeopleNum--;
		amountList.add(amount);
	}
	amountList.add(restAmount);
	return amountList;
}

问题

除了最后一次，任何一次抢到的金额都不会超过人均金额的两倍，并不是任意的随机。

思路二 线段切割法

方法

当N个人一起抢总金额为M的红包时，我们需要做N-1次随机运算，以此确定N-1个切割点。

随机的范围区间是[1，100* M）。当所有切割点确定以后，子线段的长度也随之确定。这样每个人来抢红包的时候，只需要顺次领取与子线段长度等价的红包金额即可。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static List<Integer> divide(double money, int n) {
	//验证参数合理校验
	//为了使用random.nextInt(Integer)方法不得不先把红包金额放大100倍，最后在main函数里面再除以100
	//这样就可以保证每个人抢到的金额都可以精确到小数点后两位
	int fen = (int) (money * 100);
	if (fen < n || n < 1) {
		System.out.println("红包个数必须大于0，并且最小红包不少于1分");
	}
	List<Integer> boards = new ArrayList<>();
	boards.add(0);
	boards.add(fen);
	//红包个数和板砖个数的关系
	while (boards.size() <= n) {
		int index = new Random().nextInt(fen - 1) + 1;
		if (boards.contains(index)) {
			//保证板子的位置不相同
			continue;
		}
		boards.add(index);
	}
	//计算每个红包的金额，将两个板子之间的钱加起来
	Collections.sort(boards);
	List<Integer> list = new ArrayList<>();
	for (int i = 0; i < boards.size() - 1; i++) {
		Integer e = boards.get(i + 1) - boards.get(i);
		list.add(e);
	}
	return list;
}

问题

  • 当随机切割点出现重复，如何处理。

  • 如何尽可能降低时间复杂度和空间复杂度。




标签
笔记