查找缺失的观察结果

2028。查找缺失的观察

难度：中等

主题：数组、数学、模拟

您有 n + m 个6 面 个骰子掷骰的观察结果，每个面编号为 1 到 6。n 个观察结果丢失，您只有 m 个掷骰子的观察结果。幸运的是，您还计算了 n + m 卷的平均值。

给定一个长度为 m 的整数数组 rolls，其中 rolls[i] 是第 i^th 个观察值的值。您还获得了两个整数mean和n。

返回一个长度为 n 的数组，其中包含缺失的观测值，使得 n + m 次滚动的平均值恰好等于 。如果有多个有效答案，则返回其中任何一个。如果不存在这样的数组，则返回空数组。

一组 k 个数字的平均值是这些数字的总和除以 k。

注意mean是一个整数，所以n + mrolls的总和应该能被n + m整除。

示例1：

• 输入： 卷 = [3,2,4,3]，平均值 = 4，n = 2
• 输出： [6,6]
• 解释： 所有 n + m 次掷骰的平均值为 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4。

示例2：

• 输入： 卷 = [1,5,6]，平均值 = 3，n = 4
• 输出： [2,3,2,2]
• 解释： 所有 n + m 次掷骰的平均值为 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3。

示例 3：

• 输入： 卷 = [1,2,3,4]，平均值 = 6，n = 4
• 输出： []
• 解释：无论缺少的 4 卷是多少，均值都不可能是 6。

约束：

• m == rolls.length
• 1 5
• 1

提示：

1. n 卷的总和应该是多少？
2. 你能否生成一个大小为 n 的数组，其中每个元素都在 1 到 6 之间？

解决方案：

我们需要确定一组缺失的骰子，使得所有 n + m 骰子的平均值恰好等于平均值​​。以下是解决方案的逐步分解：

接近步骤：

1. 计算 n + m 卷的总和：
   假设 n + m 次掷骰的平均值为mean，则所有掷骰的总和应为total_sum = (n + m) * Mean。

2. 确定缺失的总和：
   m 卷的总和是已知的。因此，缺失的 n 卷的总和应该是：
   

   missing_sum = total_sum - ∑(rolls)

其中 Σ(rolls) 是 rolls 数组中元素的总和。

1. 检查可行性： 每卷都是 6 面骰子，因此缺失值必须在 1 到 6 之间（含）。因此，缺失的 n 卷的总和必须介于：

   min_sum = n X 1 = n

和

   max_sum = n X 6 = 6n

如果missing_sum超出这个范围，就不可能形成有效的缺失观测值，我们应该返回一个空数组。

1. 分配缺少的金额： 如果missing_sum有效，我们通过最初用1（最小可能值）填充每个元素来将其分布在n个卷中。然后，我们将元素从 1 增加到 6，直到达到所需的 Missing_sum。

让我们用 PHP 实现这个解决方案：2028。查找缺失的观测值

<?php
/**
 * @param Integer[] $rolls
 * @param Integer $mean
 * @param Integer $n
 * @return Integer[]
 */
function missingRolls($rolls, $mean, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$rolls = [3, 2, 4, 3];
$mean = 4;
$n = 2;
print_r(missingRolls($rolls, $mean, $n));

// Example 2
$rolls = [1, 5, 6];
$mean = 3;
$n = 4;
print_r(missingRolls($rolls, $mean, $n));

// Example 3
$rolls = [1, 2, 3, 4];
$mean = 6;
$n = 4;
print_r(missingRolls($rolls, $mean, $n));
?>

解释：

1. 输入：

   • 卷 = [3, 2, 4, 3]
   • 平均值 = 4
   • n = 2

2. 步骤：

   • 总卷数为 n + m = 6。
   • 总共需要 6 * 4 = 24。
   • 给定掷骰的总和为 3 + 2 + 4 + 3 = 12。
   • 缺少的卷所需的总和是 24 - 12 = 12。

我们需要两个总和为 12 的缺失卷，唯一的可能性是 [6, 6]。

1. 结果：
   • 例如1：输出为[6, 6]。
   • 例如2：输出为[2, 3, 2, 2]。
   • 例3：无有效解，所以输出为[]。

时间复杂度：

• 计算掷骰子的总和需要 O(m)，分配 Missing_sum 需要 O(n)。因此，总体时间复杂度为 O(n + m)，这对于输入约束是有效的。

此解决方案确保我们找到有效的缺失卷或在不存在解决方案时返回空数组。

联系链接

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

以上是查找缺失的观察结果的详细内容。更多信息请关注PHP中文网其他相关文章！