3264。 K 乗算演算後の最終的な配列狀態(tài) I

難易度: 簡単

トピック: 配列、數(shù)學(xué)、ヒープ (優(yōu)先キュー)、シミュレーション

整數(shù)配列 nums、整數(shù) k、および整數(shù)乗數(shù)が與えられます。

nums に対して k 回の操作を?qū)g行する必要があります。各操作:

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

k 個(gè)の操作をすべて実行した後の nums の最終狀態(tài)を示す整數(shù)配列を返します。

例 1:

• 入力: 數(shù)値 = [2,1,3,5,6]、k = 5、乗數(shù) = 2
• 出力: [8,4,6,5,6]
• 説明:

|操作 |結(jié)果 |
|-------------------|-----------------|
|操作後 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:

• 入力: 數(shù)値 = [1,2]、k = 3、乗數(shù) = 4
• 出力: [16,8]
• 説明:

|操作 |結(jié)果 |
|-------------------|-----------------|
|操作後 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) を優(yōu)先キューに保持します。
2. 操作を k 回シミュレートします。

解決策:

問題文に記載されている操作を?qū)g裝する必要があります。主な手順は、配列內(nèi)の最小値を見つけて、指定された乗數(shù)を乗算した値に置き換え、このプロセスを k 回繰り返すことです。

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

このソリューションを PHP で実裝してみましょう: 3264。 K 乗算演算後の最終的な配列狀態(tài) 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 個(gè)の操作を?qū)g行する必要があるため、k 回ループします。
2. 最小値の検索:
   • 配列 nums を反復(fù)処理して、最小値とその 最初に出現(xiàn)するインデックスを見つけます。
3. 乗算最小値:
   • 特定されたインデックスの値を、現(xiàn)在の値と乗數(shù)の積に置き換えます。
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. 時(shí)間計(jì)算量:

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

2. 空間の複雑さ:

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

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

連絡(luò)先リンク

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

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

• LinkedIn
• GitHub

以上がK 乗算演算後の最終的な配列狀態(tài) Iの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。