红包算法

题目

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

要求:

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

  • 每个人抢到的金额数不小于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
    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