K 乗算演算後の最終的な配列状態 I

3264。 K 乗算演算後の最終的な配列状態 I

難易度: 簡単

トピック: 配列、数学、ヒープ (優先キュー)、シミュレーション

整数配列 nums、整数 k、および整数乗数が与えられます。

nums に対して k 回の操作を実行する必要があります。各操作:

• nums の最小値 x を求めます。最小値が複数ある場合は、最初に出現したものを選択します。
• 選択した最小値 x を x * 乗数に置き換えます。

k 個の操作をすべて実行した後の nums の最終状態を示す整数配列を返します。

例 1:

• 入力: 数値 = [2,1,3,5,6]、k = 5、乗数 = 2
• 出力: [8,4,6,5,6]
• 説明:

|操作 |結果 |
|-------------------|-----------------|
|操作後 1 | [2、2、3、5、6] |
|操作後 2 | [4、2、3、5、6] |
|操作後 3 | [4、4、3、5、6] |
|操作後 4 | [4、4、6、5、6] |
|操作後 5 | [8、4、6、5、6] |

例 2:

• 入力: 数値 = [1,2]、k = 3、乗数 = 4
• 出力: [16,8]
• 説明:

|操作 |結果 |
|-------------------|-----------------|
|操作後 1 | [2、2、3、5、6] |
|操作後 2 | [4、2、3、5、6] |
|操作後 3 | [4、4、3、5、6] |
|操作後 4 | [4、4、6、5、6] |
|操作後 5 | [8、4、6、5、6] |

制約:

• 1
• 1
• 1
• 1

ヒント:

1. ソートされたペア (nums[index]、index) を優先キューに保持します。
2. 操作を k 回シミュレートします。

解決策:

問題文に記載されている操作を実装する必要があります。主な手順は、配列内の最小値を見つけて、指定された乗数を乗算した値に置き換え、このプロセスを k 回繰り返すことです。

最初に出現した最小値を選択して置き換える必要があるとすると、各操作中に最小値のインデックスを追跡することでこれに取り組むことができます。 PHP 実装では、優先キュー (最小ヒープ) を使用して、各操作中に最小値を効率的に取得および更新します。

このソリューションを PHP で実装してみましょう: 3264。 K 乗算演算後の最終的な配列状態 I

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @param Integer $multiplier
 * @return Integer[]
 */
function finalArrayState($nums, $k, $multiplier) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test Case 1
$nums1 = [2, 1, 3, 5, 6];
$k1 = 5;
$multiplier1 = 2;
$result1 = finalArrayState($nums1, $k1, $multiplier1);
echo "Output: [" . implode(", ", $result1) . "]\n";

// Test Case 2
$nums2 = [1, 2];
$k2 = 3;
$multiplier2 = 4;
$result2 = finalArrayState($nums2, $k2, $multiplier2);
echo "Output: [" . implode(", ", $result2) . "]\n";
?>

説明：

1. 初期化: k 個の操作を実行する必要があるため、k 回ループします。
2. 最小値の検索:
   • 配列 nums を反復処理して、最小値とその 最初に出現するインデックスを見つけます。
3. 乗算最小値:
   • 特定されたインデックスの値を、現在の値と乗数の積に置き換えます。
4. 繰り返し:
   • 上記の手順を k 回繰り返します。
5. 最終配列を返します:
   • すべての操作後に変更された配列を返します。

テスト出力

提供されたテスト ケースの場合:

テストケース 1:

入力:

$nums = [2, 1, 3, 5, 6];
$k = 5;
$multiplier = 2;

出力:

Output: [8, 4, 6, 5, 6]

テストケース 2:

入力:

$nums = [1, 2];
$k = 3;
$multiplier = 4;

出力:

Output: [16, 8]

複雑

1. 時間計算量:

   • k 個の演算のそれぞれについて、配列内の最小値を見つけるには O(n) が必要です。
   • 合計: O(k x n)、n は配列のサイズです。

2. 空間の複雑さ:

   • このソリューションでは、O(1) の余分なスペースが使用されます。

このソリューションは制約を遵守し、すべてのテスト ケースで期待される結果を提供します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がK 乗算演算後の最終的な配列状態 Iの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。