抢红包的两种算法

 文章最前： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

1.利用二倍均值的方式进行红包的划分

   /**
     * 二倍均值法生成红包
     *
     * @param person 人的数量
     * @param money  钱的数量
     * @return 红包链表
     */
    private List<Integer> generatePacketsByDoubleMean(int person, int money) {
        List<Integer> list = new ArrayList<>();
        Random ran = new Random();
        while (person > 1) {
            int num = ran.nextInt(2 * (money / person));
            list.add(num);
            money = money - num;
            person--;
        }
        list.add(money);
        return list;
    }

时间复杂度：O(n)

空间复杂度：O(n)

2.一条线段上标记n-1个点，然后按照每个点剪断，就得到了随机数

   /**
     * 生成抢红包链表
     *
     * @param person 人的数量
     * @param money  钱的数量
     * @return 红包链表
     */
    private List<Double> generateDoublePacketsByLineCutting(int person, int money) {
        List<Double> packets = new ArrayList<>();
        Random random = new Random();
        Set<Double> points = new TreeSet<>();
        while (points.size() < person - 1) {
            // 找到n-1个点
            Double num = (int) Math.round(random.nextDouble() * (money - 1) * 100) / 100.0;
            points.add(num);
        }
        // 记录最后一个点
        points.add(Double.valueOf(money));
        Double proPoint = 0d;
        for (Double point : points) {
            // 最后进行求值取差计算
            Double num2 = (int) Math.round(random.nextDouble() * (point - proPoint) * 100) / 100.0;
            packets.add(num2);
            proPoint = point;
        }
        return packets;
    }

时间复杂度：O(n)

空间复杂度：O(n)