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

解法

方法一：优先队列（小根堆）+ 模拟

我们可以用一个小根堆来维护数组 $\textit{nums}$ 中的元素，每次从小根堆中取出最小值，将其乘以 $\textit{multiplier}$ 后再放回小根堆中。在实现过程中，我们往小根堆插入的是元素的下标，然后自定义比较函数，使得小根堆按照 $\textit{nums}$ 中元素的大小作为第一关键字，下标作为第二关键字进行排序。

最后，我们返回数组 $\textit{nums}$ 即可。

时间复杂度 $O((n + k) \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\textit{nums}$ 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        pq = [(x, i) for i, x in enumerate(nums)]
        heapify(pq)
        for _ in range(k):
            _, i = heappop(pq)
            nums[i] *= multiplier
            heappush(pq, (nums[i], i))
        return nums

class Solution {
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        PriorityQueue<Integer> pq
            = new PriorityQueue<>((i, j) -> nums[i] - nums[j] == 0 ? i - j : nums[i] - nums[j]);
        for (int i = 0; i < nums.length; i++) {
            pq.offer(i);
        }
        while (k-- > 0) {
            int i = pq.poll();
            nums[i] *= multiplier;
            pq.offer(i);
        }
        return nums;
    }
}

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        auto cmp = [&nums](int i, int j) {
            return nums[i] == nums[j] ? i > j : nums[i] > nums[j];
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

        for (int i = 0; i < nums.size(); ++i) {
            pq.push(i);
        }

        while (k--) {
            int i = pq.top();
            pq.pop();
            nums[i] *= multiplier;
            pq.push(i);
        }

        return nums;
    }
};

func getFinalState(nums []int, k int, multiplier int) []int {
    h := &hp{nums: nums}
    for i := range nums {
        heap.Push(h, i)
    }

    for k > 0 {
        i := heap.Pop(h).(int)
        nums[i] *= multiplier
        heap.Push(h, i)
        k--
    }

    return nums
}

type hp struct {
    sort.IntSlice
    nums []int
}

func (h *hp) Less(i, j int) bool {
    if h.nums[h.IntSlice[i]] == h.nums[h.IntSlice[j]] {
        return h.IntSlice[i] < h.IntSlice[j]
    }
    return h.nums[h.IntSlice[i]] < h.nums[h.IntSlice[j]]
}

func (h *hp) Pop() any {
    old := h.IntSlice
    n := len(old)
    x := old[n-1]
    h.IntSlice = old[:n-1]
    return x
}

func (h *hp) Push(x any) {
    h.IntSlice = append(h.IntSlice, x.(int))
}

function getFinalState(nums: number[], k: number, multiplier: number): number[] {
    const pq = new PriorityQueue({
        compare: (i, j) => (nums[i] === nums[j] ? i - j : nums[i] - nums[j]),
    });
    for (let i = 0; i < nums.length; ++i) {
        pq.enqueue(i);
    }
    while (k--) {
        const i = pq.dequeue()!;
        nums[i] *= multiplier;
        pq.enqueue(i);
    }
    return nums;
}

3264. K 次乘运算后的最终数组 I

题目描述

解法

方法一：优先队列（小根堆）+ 模拟

评论