What is the best approach to solving Find Missing Observations?

The best approach is to first calculate the total sum of all rolls based on the given mean, then check if the missing rolls can be distributed in a way that maintains the mean.

How do I handle edge cases where the mean cannot be achieved?

You must validate if the sum of the missing rolls is feasible by ensuring it falls within the range of possible sums (between n and n*6). If not, return an empty array.

What if there are multiple valid solutions for the missing rolls?

The problem allows multiple valid solutions. Any array that meets the requirements is acceptable as a correct answer.

What topics are covered by the Find Missing Observations problem?

The problem covers array manipulation, basic math operations, and simulation techniques to calculate missing values and validate them.

How do I improve my solution for larger inputs?

For larger inputs, focus on optimizing the validation steps to avoid unnecessary checks. The solution should be efficient with respect to both time and space complexity.

#2028

Medium

auto_awesome数组·数学

LeetCode 题解工作台

找出缺失的观测数据

现有一份 n + m 次投掷单个六面骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的平均值。给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测…

数组数学模拟

题目描述

现有一份 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

lightbulb

解题思路

方法一：构造

根据题目描述，所有数字之和为 $(n + m) \times \textit{mean}$ ，已知的数字之和为 $\sum_{i=0}^{m-1} \textit{rolls}[i]$ ，那么缺失的数字之和为 $s = (n + m) \times \textit{mean} - \sum_{i=0}^{m-1} \textit{rolls}[i]$ 。

如果 $s \gt n \times 6$ 或者 $s \lt n$ ，说明不存在满足条件的答案，返回空数组。

否则，我们可以将 $s$ 平均分配到 $n$ 个数字上，即每个数字的值为 $s / n$ ，其中 $s \bmod n$ 个数字的值再加上 $1$ 。

时间复杂度 $O(n + m)$ ，其中 $n$ 和 $m$ 分别为缺失的数字个数和已知的数字个数。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        s = (n + m) * mean - sum(rolls)
        if s > n * 6 or s < n:
            return []
        ans = [s // n] * n
        for i in range(s % n):
            ans[i] += 1
        return ans

speed

复杂度分析

指标	值
时间	O(m + n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate can handle basic array operations and sum calculations.
question_mark
Observe whether the candidate is able to handle edge cases where the mean can't be met.
question_mark
Evaluate if the candidate can implement efficient validation for the missing rolls.

warning

常见陷阱

外企场景

error
Misunderstanding the constraint that each missing roll must be between 1 and 6.
error
Not checking if the sum of missing rolls is possible before attempting to fill the array.
error
Failing to return an empty array when the mean cannot be achieved.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider handling cases where the number of missing rolls is large, testing the efficiency of the solution.
arrow_right_alt
Modify the problem to have a varying range of possible values (not just 1 to 6).
arrow_right_alt
Add constraints where some rolls can be negative or fractional values, increasing the complexity.

help

常见问题

外企场景

继续练习

#2221 数组的三角和 #1823 找出游戏的获胜者 #1806 还原排列的最少操作步数