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

<?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 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是K 乘法运算后的最终数组状态 I的详细内容。更多信息请关注PHP中文网其他相关文章！