找出缺失的观测数据

难度: Medium

现有一份 n + m 次投掷单个六面骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。

给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。

返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。

k 个数字的 平均值 为这些数字求和后再除以 k 。

注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。

示例 1：

输入：rolls = [3,2,4,3], mean = 4, n = 2
输出：[6,6]
解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。

示例 2：

输入：rolls = [1,5,6], mean = 3, n = 4
输出：[2,3,2,2]
解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。

示例 3：

输入：rolls = [1,2,3,4], mean = 6, n = 4
输出：[]
解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。

示例 4：

输入：rolls = [1], mean = 3, n = 1
输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。

提示：

m == rolls.length
1 <= n, m <= 10⁵
1 <= rolls[i], mean <= 6

Submission

运行时间: 57 ms

内存: 21.2 MB

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        rolls_sum = sum(rolls)
        m = len(rolls)
        real_sum = mean * (m+n)
        diff = real_sum - rolls_sum
        if not (n*1 <= diff <= 6*n):
            return []
        average = diff // n
        resi = diff % n
        return [average + 1] * resi + [average] * (n - resi)
         #  diff = resi + average * n
         # diff = (average +1) * resi + average * (n - resi)

Explain

首先计算已有观测数据的总和 rolls_sum，然后根据总的平均值 mean 和投掷次数 (n + m) 计算所有投掷的理论总和 real_sum。接下来，差值 diff 是丢失的 n 次投掷的总和，即 real_sum - rolls_sum。检查这个 diff 是否在合理的范围内，即 n * 1（每次最少投出1点）和 n * 6（每次最多投出6点）之间。如果不在这个范围内，则没有可能的解，返回空数组。如果在范围内，计算每次投掷的平均值 average 为 diff // n 并计算余数 resi = diff % n。余数 resi 表示有多少个投掷需要比平均值多出1。最后，构造结果数组，包含 resi 个 (average + 1) 和 (n - resi) 个 average。

时间复杂度: O(max(m, n))

空间复杂度: O(n)

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        rolls_sum = sum(rolls)  # 计算已有数据的总和
        m = len(rolls)  # 已有数据的个数
        real_sum = mean * (m + n)  # 计算所有数据的理论总和
        diff = real_sum - rolls_sum  # 计算缺失数据的总和
        if not (n * 1 <= diff <= 6 * n):
            return []  # 如果总和不在合理范围内，返回空数组
        average = diff // n  # 计算缺失数据的平均值
        resi = diff % n  # 计算需要额外加1的数据个数
        return [average + 1] * resi + [average] * (n - resi)  # 构造结果数组，包含 resi 个 (average + 1) 和 (n - resi) 个 average

Explore

在`missingRolls`函数中，`rolls_sum`是已有观测数据的总和，它直接影响通过总平均`mean`计算出的所有投掷次数（包括缺失的和已知的）的理论总和`real_sum`。通过比较`rolls_sum`和`real_sum`，我们得到缺失数据的总和`diff`。这个`diff`是补全缺失数据的关键，因此`rolls_sum`是连接输入数据和缺失数据解决方案的桥梁。

`diff`的值不总是保证在`n * 1`至`n * 6`的范围内。这个范围是基于每次投掷的最小值为1和最大值为6的假设。如果`diff`不在这个范围内，表示无法通过正常的骰子投掷得到这样的总和，因此在当前模型下没有解决方案。如果`diff`超出了这个范围，理论上我们需要考虑修改投掷次数或重新计算平均值，但这通常不符合问题的设定，因此通常返回空数组表示无解。

`diff // n`和`diff % n`的使用是为了公平合理地分配缺失的观测数据。`diff // n`计算每次投掷的基础平均值，而`diff % n`确定有多少次投掷需要额外增加一个点数以使总和达到`diff`。这种方法试图尽可能均匀地分配值，但在某些情况下可能会导致分配不均，尤其是在`n`很大而`diff`相对较小的情况下。然而，在大多数情况下，这种方法是合理的，因为它确保了所有值都在1到6的有效范围内。

在标准设定下，`average + 1`的值有可能超过骰子的最大面值6。这通常发生在`diff`相对于`n`非常大的情况下。如果`average + 1`超过了6，这意味着没有可能的方法将`diff`均匀分配到`n`次投掷中，每次投掷结果都在1到6之间。在这种情况下，算法应返回一个空数组，表示没有合法的解决方案能够满足所有条件。