红包算法

Posted on Edited on Views: Waline:

题目

给定一个红包总金额和分红包的人数，输出每个人随机抢到的红包数量。

要求:

  • 每个人都要抢到红包，并且金额随机。

  • 每个人抢到的金额数不小于1

  • 每个人抢到的金额数不超过总金额的30%

    例如总金额100，人数10，输出【19 20 15 1 25 14 2 2 1 1】

思路

  1. 首先是这个人数必须要大于等于4，否则直接都不满足第三个条件

  2. new 一个数组，让这个数据的每个数据都等于1

  3. new一个随机数在1到30之间

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

    public static void main(String[] args) {

        int total=0;

        int count=50000;

        for (int i = 0; i < count; i++) {

            int packet = getPacket(100, 10);

            total=total+packet;

        }

        //这个是来测试这段代码的性能，基本上在count=50的时候，已经稳定在了15了，时间复杂度基本上可以说是1.5N，N就是人员的数量

        System.out.println(total/count);



//        for (int i : packet) {

//            System.out.print(i+",");

//        }

    }

    public static int getPacket(int money,int number){

        if(number < 4 || money < number){

            throw new IllegalArgumentException("illegal argument");

        }

        int[] result = new int[number];

        for (int i = 0; i < number; i++) {

            result[i] = 1;

        }

        double threshold = money * 0.3;

        int remain = money - number;

        int index = 0;

        Random random = new Random();

        int count=0;

        while (remain > 0){

            int i = random.nextInt(remain);

            if(i == 0){

                i = 1;

            }

            double now = result[index] + i;

            if(now <= threshold){

                result[index] = (int)now;

                remain -= i;

            }

            index ++;

            count++;

            if(index == number){

                index = 0;

            }

        }

        //System.out.println(count);

        return count;

    }

收获

  1. 在所有数据都有一个最小值的数据的情况下，可以假设所有的值都是最小值，在此基础至上，来进行数据处理

  2. random.nextInt（x）的方法，返回(0,x],即大于0小于等于x