K 乘法運算後的最終陣列狀態 I

3264。 K 乘法運算後的最終陣列狀態 I

難度：簡單

主題：陣列、數學、堆疊（優先隊列）、模擬

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

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

• 求 nums 中的最小值 x。如果最小值多次出現，請選擇第一個出現的那個。
• 用 x * 乘數取代所選的最小值 x。

回傳一個整數數組，表示執行所有k個操作後nums的最終狀態.

範例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. 在優先權佇列中維護排序對 (nums[index], index)。
2. 模擬操作k次。

解：

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

鑑於我們需要選擇第一次出現的最小值並替換它，我們可以透過在每次操作期間追蹤最小值的索引來實現這一點。 PHP 實作將使用優先權佇列（最小堆）來有效地檢索和更新每次操作期間的最小值。

讓我們用 PHP 實作這個解：3264。 K 乘法運算後的最終陣列狀態 I

解釋：

1. 初始化：循環k次，因為需要執行k次操作。
2. 求最小值：
   • 迭代數組 nums 以找到最小值及其首次出現索引.
3. 乘以最小值：
   • 以目前值與乘數的乘積取代已辨識索引處的值。
4. 重複：
   • 重複上述步驟進行 k 次迭代。
5. 傳回最終數組：
   • 所有操作後傳回修改後的陣列。

測試輸出

對於提供的測試案例：

測試案例1：

輸入：

輸出：

測試案例2：

輸入：

輸出：

複雜

1. 時間複雜度:

   • 對於 k 次操作中的每一個，找到陣列中的最小值都需要 O(n)。
   • 總計：O(k x n)，其中 n 是陣列的大小。

2. 空間複雜度:

   • 此解決方案使用 O(1) 額外空間。

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

聯絡連結

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

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

• 領英
• GitHub

以上是K 乘法運算後的最終陣列狀態 I的詳細內容。更多資訊請關注PHP中文網其他相關文章！