Easy

题目描述

给你一个整数数组 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

提示：

  • 在优先队列中维护排序的对 (nums[index], index)。
  • 模拟操作 k 次。

解题思路

这道题有两种主要的解法思路：

方法一：暴力模拟（推荐）

最直接的方法是按题意模拟整个过程。每次找到数组中的最小值（如果有多个最小值，选择索引最小的），然后将其乘以 multiplier。重复 k 次即可。

由于数组长度和 k 都很小（最大100和10），这种方法完全可行。每次操作的时间复杂度是 O(n)，总时间复杂度为 O(k*n)。

方法二：优先队列优化

使用最小堆来维护 (值, 索引) 对，这样可以快速找到最小值。当值相同时，索引小的优先。每次从堆顶取出最小元素，更新后再放回堆中。

这种方法的时间复杂度为 O(nlog(n) + klog(n))，在数据量较大时会更优。

考虑到题目的约束条件（n≤100, k≤10），方法一的暴力模拟更简洁直观，是更好的选择。

代码实现

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        for (int i = 0; i < k; i++) {
            int minIdx = 0;
            for (int j = 1; j < nums.size(); j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            nums[minIdx] *= multiplier;
        }
        return nums;
    }
};

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        for _ in range(k):
            min_idx = 0
            for i in range(1, len(nums)):
                if nums[i] < nums[min_idx]:
                    min_idx = i
            nums[min_idx] *= multiplier
        return nums

public class Solution {
    public int[] GetFinalState(int[] nums, int k, int multiplier) {
        for (int i = 0; i < k; i++) {
            int minIdx = 0;
            for (int j = 1; j < nums.Length; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            nums[minIdx] *= multiplier;
        }
        return nums;
    }
}

var getFinalState = function(nums, k, multiplier) {
    for (let i = 0; i < k; i++) {
        let minIdx = 0;
        for (let j = 1; j < nums.length; j++) {
            if (nums[j] < nums[minIdx]) {
                minIdx = j;
            }
        }
        nums[minIdx] *= multiplier;
    }
    return nums;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度暴力模拟优先队列
时间复杂度O(k × n)O(n log n + k log n)
空间复杂度O(1)O(n)

其中 n 是数组长度，k 是操作次数。在本题约束条件下（n ≤ 100, k ≤ 10），暴力模拟方法更优。