[LeetCode] 每日一题 3264. K 次乘运算后的最终数组 I

题目链接

题目描述

给你一个整数数组 nums ，一个整数 k  和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

• 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。

• 将 x 替换为 x * multiplier 。

请你返回执行完 k 次乘运算之后，最终的 nums 数组。

示例输入

示例 1

输入：nums = [2,1,3,5,6], k = 5, multiplier = 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, multiplier = 4

输出：[16,8]

解释：
操作	结果
1 次操作后	[4, 2]
2 次操作后	[4, 8]
3 次操作后	[16, 8]

提示

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 100

• 1 <= k <= 10

• 1 <= multiplier <= 5

题解

解题思路

• 处理边界情况：

  • 如果 multiplier == 1，无论操作多少次，数组中的元素不会变化，因为乘以 1 不会改变任何值。因此，我们可以直接返回原数组。

• 查找最小值并替换：

  • 我们需要找到数组中最小的元素（如果有多个相等的最小值，选择最前面的）。

  • 对这个最小值进行乘法操作，并替换原数组中的该位置的值。

  • 重复进行上述操作 k 次。

• 效率：

  • 每次操作我们需要遍历整个数组找到最小值，因此每次操作的时间复杂度是 O(n)，其中 n 是数组的大小。

  • 进行 k 次操作时，时间复杂度为 O(k * n)。

代码实现

class Solution {
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        // 如果 multiplier 是 1，直接返回 nums，不需要任何操作
        if (multiplier == 1) {
            return nums;
        }
        
        // 执行 k 次操作
        while (k-- > 0) {
            // 找到数组中的最小值，记录其索引
            int minIndex = 0;
            for (int i = 1; i < nums.length; i++) {
                if (nums[minIndex] > nums[i]) {
                    minIndex = i;
                }
            }
            // 将最小值乘以 multiplier
            nums[minIndex] *= multiplier;
        }
        
        // 返回最终数组
        return nums;
    }
}

复杂度分析

时间复杂度

• 每次操作需要遍历整个数组来寻找最小值，时间复杂度是 O(n)，其中 n 是数组的长度。

• 进行 k 次操作，总时间复杂度为 O(k * n)。

空间复杂度

• 由于我们只使用了常数空间来存储索引和临时变量，因此空间复杂度为 O(1)。

总结

通过逐步找到数组中的最小值并进行更新，解决了这个题目。虽然时间复杂度是 O(k * n)，但对于数组大小和 k 的值较小的情况，性能是可以接受的。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。