LeetCode-2028-找出缺失的观测数据

题目描述

看到题目其实很快就能想到思路
(现有数据的长度 + 缺失的长度) * 平均值 = 数据的总和
如果 数据的总和 - 现有数据的总和 > 缺失的长度 * 骰子的最大值6 则代表没有这么多的空间可以容纳，返回空数组就可以了

最大的问题在于当 数据的总和 - 现有数据的总和 < 缺失的长度 * 骰子的最大值6 时，这个时候会出现一种情况
比如 数据的总和 - 现有数据的总和 = 19， 缺失的长度为5， 那么很容易就能得到这是有解的，能想到返回解是[3,4,4,4,4]是最方便的，但是19/5=3，如何变成4就是最影响效率的事情

示例代码

public int[] missingRolls(int[] rolls, int mean, int n) {
        int rLen = rolls.length;
        int sumLen = rLen + n;
        int sum = mean * sumLen;

        int rSum = 0;
        for(int r : rolls){
            rSum += r;
        }

        if((sum-rSum) > 6*n || (sum-rSum) < n){
            return new int[0];
        }else{
            int[] res = new int[n];
            int temp = 0;
            for(int i=0; i<n; i++){
                res[i] = (sum-rSum)/n;
                temp += (sum-rSum)/n;
            }
            int temp2 = (sum-rSum) - temp;
            for(int i=0; i<temp2; i++){
                res[i] = res[i]+1;
            }

            return res;
        }
    }

结合对题目的分析，可以知道

这部分代码是最影响效率的，上述代码分配的方法是先按照取余进行分配，分配之后剩下的数，在从头开始依次加1，这里也贴出官解的代码

public int[] missingRolls(int[] rolls, int mean, int n) {
    int m = rolls.length;
    int sum = mean * (n + m);
    int missingSum = sum;
    for (int roll : rolls) {
        missingSum -= roll;
    }
    if (missingSum < n || missingSum > 6 * n) {
        return new int[0];
    }
    int quotient = missingSum / n, remainder = missingSum % n;
    int[] missing = new int[n];
    for (int i = 0; i < n; i++) {
        missing[i] = quotient + (i < remainder ? 1 : 0);
    }
    return missing;
}

业务场景

分配的过程，也是kafka 分区分配策略里的 range