查找缺失的觀察結果

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)，這對於輸入限制是有效的。

此解決方案確保我們找到有效的缺失磁碟區或在不存在解決方案時傳回空數組。

聯絡連結

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

以上是查找缺失的觀察結果的詳細內容。更多資訊請關注PHP中文網其他相關文章！