抢红包的两种算法

偏执的太偏执、 2022-03-29 09:11 243阅读 0赞

> ** 文章最前**： 我是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)

[github]: https://github.com/zhangyu345293721