欠けている観測値を見つける

2028年。欠けている観測値を見つける

難易度: 中

トピック: 配列、数学、シミュレーション

n + m 個の 6 面 個のサイコロのロールの観測値があり、各面には 1 から 6 までの番号が付けられています。n 個の観測値が欠落しており、m 個のロールの観測値しかありません。幸いなことに、n + m 回のロールの 平均値 も計算できました。

長さ m の整数配列 rolls が与えられます。ここで、rolls[i] は i ^番目 の観測値です。また、2 つの整数の means と n も与えられます。

n + m ロールの平均値が正確に平均となるような、欠落している観測値を含む長さ n の配列を返します。有効な回答が複数ある場合は、いずれかを返します。そのような配列が存在しない場合は、空の配列を返します。

k 個の数値セットの 平均値 は、数値の合計を k で割った値です。

注意では、mean は整数であるため、n + mroll の合計は 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 == ロールの長さ
• 1 5
• 1

ヒント:

1. n ロールの合計はいくらになるでしょうか?
2. 各要素が 1 から 6 の間になるようなサイズ n の配列を生成してもらえますか?

解決策:

すべての n + m 個のサイコロの出目の平均が平均と正確に等しくなるように、欠落している出目の配列を決定する必要があります。ソリューションの段階的な内訳は次のとおりです:

アプローチの手順:

1. n + m ロールの合計を計算します:
   n + m ロールの平均値が平均であるとすると、すべてのロールの合計は total_sum = (n + m) * means.

となるはずです。

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 個のロールに分散します。次に、必要な missing_sum に達するまで、要素を 1 から 6 まで増やします。

このソリューションを 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 になる 2 つの不足しているロールが必要です。唯一の可能性は [6, 6] です。

1. 結果:
   • 例 1: 出力は [6, 6] です。
   • 例 2: 出力は [2, 3, 2, 2] です。
   • 例 3: 有効な解決策がないため、出力は [] になります。

時間計算量:

• ロールの合計の計算には O(m) かかり、missing_sum の分配には O(n) かかります。したがって、全体的な時間計算量は O(n + m) となり、入力制約に対して効率的です。

このソリューションは、有効な欠落ロールを見つけるか、ソリューションが存在しない場合は空の配列を返すことを保証します。

連絡先リンク

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

以上が欠けている観測値を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。