LeetCode 题解工作台
K 次乘运算后的最终数组 II
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。 你需要对 nums 执行 k 次操作，每次操作中： 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。 将 x 替换为 x * multiplier 。 k 次操作以后，你需要将 nums…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 堆
答案摘要
我们记数组 的长度为 ，最大值为 。 我们首先通过利用优先队列（小根堆），模拟操作，直到完成 次操作或者堆中所有元素都大于等于 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。
你需要对 nums 执行 k 次操作，每次操作中：
- 找到
nums中的 最小 值x，如果存在多个最小值，选择最 前面 的一个。 - 将
x替换为x * multiplier。
k 次操作以后，你需要将 nums 中每一个数值对 109 + 7 取余。
请你返回执行完 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] |
| 取余操作后 | [8, 4, 6, 5, 6] |
示例 2：
输入：nums = [100000,2000], k = 2, multiplier = 1000000
输出：[999999307,999999993]
解释：
| 操作 | 结果 |
|---|---|
| 1 次操作后 | [100000, 2000000000] |
| 2 次操作后 | [100000000000, 2000000000] |
| 取余操作后 | [999999307, 999999993] |
提示：
1 <= nums.length <= 1041 <= nums[i] <= 1091 <= k <= 1091 <= multiplier <= 106
解题思路
方法一：优先队列（小根堆）+ 模拟
我们记数组 的长度为 ，最大值为 。
我们首先通过利用优先队列（小根堆），模拟操作，直到完成 次操作或者堆中所有元素都大于等于 。
此时，数组所有元素值都小于 ，由于 且 ，所以 ，是在 位整数范围内的。
接下来，我们的每一次操作，都会将数组中的最小元素变成最大元素，因此在每 次连续操作后，数组中的每个元素都恰好执行了一次乘法操作。
因此，我们在模拟过后，剩余 次操作，那么数组中最小的 个元素将会执行 次乘法操作，其余的元素将会执行 次乘法操作。
最后，我们将数组中的每个元素乘上对应的乘法次数，再取模 即可，可以通过快速幂来计算。
时间复杂度 ，空间复杂度 。其中 为数组 的长度，而 为数组 中的最大值。
class Solution:
def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
if multiplier == 1:
return nums
pq = [(x, i) for i, x in enumerate(nums)]
heapify(pq)
m = max(nums)
while k and pq[0][0] < m:
x, i = heappop(pq)
heappush(pq, (x * multiplier, i))
k -= 1
n = len(nums)
mod = 10**9 + 7
pq.sort()
for i, (x, j) in enumerate(pq):
nums[j] = x * pow(multiplier, k // n + int(i < k % n), mod) % mod
return nums
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates proficiency in heap operations and optimization techniques.
- question_mark
Candidate's approach handles large values of k efficiently without excessive overhead.
- question_mark
Candidate explains the trade-offs between different heap-based solutions, considering both time and space complexity.
常见陷阱
外企场景- error
Failing to apply the modulo operation after each multiplication, leading to overflow.
- error
Incorrectly updating the heap, causing inefficient operation due to rebalancing.
- error
Misunderstanding the impact of large k values, leading to inefficiencies in the solution.
进阶变体
外企场景- arrow_right_alt
Consider a variant where the multiplier is a dynamic value, changing between operations.
- arrow_right_alt
A version where elements are updated based on other conditions besides the minimum, like the maximum or random elements.
- arrow_right_alt
Optimize for cases where k is relatively small, reducing the reliance on heaps.