3264。 K 乘法運算后的最終數組狀態(tài) I

難度：簡單

主題：數組、數學、堆（優(yōu)先級隊列）、模擬

給你一個整數數組 nums、一個整數 k 和一個整數乘數。

您需要對 nums 執(zhí)行 k 次操作。在每個操作中：

• 求 nums 中的最小值 x。如果最小值多次出現(xiàn)，請選擇第一個出現(xiàn)的那個。
• 用 x * 乘數替換所選的最小值 x。

返回一個整數數組，表示執(zhí)行所有k個操作后nums的最終狀態(tài).

示例1：

• 輸入： nums = [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：

• 輸入： nums = [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. 在優(yōu)先級隊列中維護排序對 (nums[index], index)。
2. 模擬操作k次。

解決方案：

我們需要實現(xiàn)問題陳述中描述的操作。關鍵步驟是找到數組中的最小值，將其替換為乘以給定乘數的值，然后重復此過程 k 次。

鑒于我們需要選擇第一次出現(xiàn)的最小值并替換它，我們可以通過在每次操作期間跟蹤最小值的索引來實現(xiàn)這一點。 PHP 實現(xiàn)將使用優(yōu)先級隊列（最小堆）來有效地檢索和更新每次操作期間的最小值。

讓我們用 PHP 實現(xiàn)這個解決方案：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. 初始化：循環(huán)k次，因為需要執(zhí)行k次操作。
2. 求最小值：
   • 迭代數組 nums 以查找最小值及其首次出現(xiàn)索引.
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) 額外空間。

該解決方案遵守約束條件，并為所有測試用例提供預期結果。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是K 乘法運算后的最終數組狀態(tài) I的詳細內容。更多信息請關注PHP中文網其他相關文章！