Skip to content

Latest commit

 

History

History
262 lines (209 loc) · 5.99 KB

README.md

File metadata and controls

262 lines (209 loc) · 5.99 KB
comments difficulty edit_url rating source tags
true
简单
1177
第 412 场周赛 Q1
数组
数学
模拟
堆（优先队列）

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

English Version

题目描述

给你一个整数数组 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}$ 的长度。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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))
}

TypeScript

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;
}