3266. Final Array State After K Multiplication Operations II
Problem
You are given an integer array nums, an integer k, and an integer multiplier.
You need to perform k operations on nums. In each operation:
- Find the minimum value
xinnums. If there are multiple occurrences of the minimum value, select the one that appears first. - Replace the selected minimum value
xwithx * multiplier.
After the k operations, apply modulo 10⁹ + 7 to every value in nums.
Return an integer array denoting the final state of nums after performing all k operations and then applying the modulo.
https://leetcode.cn/problems/final-array-state-after-k-multiplication-operations-ii/
Example 1:
Input:
nums = [2,1,3,5,6], k = 5, multiplier = 2
Output:[8,4,6,5,6]
Explanation:
Operation Result After operation 1 [2, 2, 3, 5, 6]After operation 2 [4, 2, 3, 5, 6]After operation 3 [4, 4, 3, 5, 6]After operation 4 [4, 4, 6, 5, 6]After operation 5 [8, 4, 6, 5, 6]
Example 2:
Input:
nums = [100000,2000], k = 2, multiplier = 1000000
Output:[999999307,999999993]
Explanation:
Operation Result After operation 1 [100000, 2000000000]After operation 2 [100000000000, 2000000000]After applying modulo [999999307, 999999993]
Constraints:
1 <= nums.length <= 10⁴1 <= nums[i] <= 10⁹1 <= k <= 10⁹1 <= multiplier <= 10⁶
Test Cases
class Solution:
def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:import pytest
from solution import Solution
@pytest.mark.parametrize('nums, k, multiplier, expected', [
([2,1,3,5,6], 5, 2, [8,4,6,5,6]),
([100000,2000], 2, 1000000, [999999307,999999993]),
([1,2], 3, 4, [16,8]),
([2,5,1,5,1,1,3,5], 5, 2, [4,5,4,5,2,2,3,5]),
([1,1,1000000000], 3, 1000000, [999993007,1000000,1000000000]),
([66307295,441787703,589039035,322281864], 900900704, 641725, [664480092, 763599523, 886046925, 47878852]),
([889458628,338743558,875422936,684907163,233489834], 246181588, 313380, [940635593,321154185,859014034,48349682,391180073]),
(
[3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489],
1000000000, 3,
[869770420,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809]
),
(
[2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912],
1000000000, 2,
[112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914]
),
(
[5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625],
1000000000, 5,
[676863159,676863159,676863159,676863159,676863159,676863159,676863159,676863159,676863159,676863159,735372636,735372636]
),
])
class Test:
def test_solution(self, nums, k, multiplier, expected):
sol = Solution()
assert sol.getFinalState(nums.copy(), k, multiplier) == expected
Thoughts
这可能是提交遇到解答错误次数最多的一题了。
3264. Final Array State After K Multiplication Operations I 的进阶版。不只是 n = nums.length 从 100 提升到 10⁴，k 也从 10 提升到了 10⁹。
Huge “k”
先看变得更大的 k，从 1 遍历到 k 肯定是跑不动的。但这个跟 1760. Minimum Limit of Balls in a Bag 非常像（指最大堆的那种实现方式，而非二分法），巨大的 k 其实会给每个数字都平摊很多，可以先计算出每个数字平摊多少，直接乘上去，可以省掉大量的循环。
设 nums 中的最大值为 top。先把所有其他数字通过乘以 multiplier 的某个次方，增大到不超过 top，即修改之后的数组满足：对于任意的 i，nums[i] <= top < nums[i] * multiplier。设某个数字是 v，那么 p = ⌊log(top / v, multiplier)⌋，让 v 乘以 multiplier 的 p 次方即可。
这里有个坑，在 Python 里直接计算
log(a, b)结果可能会有些偏差，导致下取整会少 1。比如log(3**17, 3) = 16.999999999999996，比如log10(5**7) / log10(5) = 6.999999999999999。即使用 decimal 也同样会遇到 bad case。目前的处理方法是计算完之后根据情况修正一下：def ilog(a: int, b: int) -> int: """Calculates int(log(a, b)).""" p = int(log10(a) / log10(b)) if b ** (p + 1) <= a: p += 1 return p
可以发现这个状态下，每连续 n 次操作就刚好给 nums 中每个数字都乘以 multiplier 一次。设前边为了达到这个状态需要 t 次操作，那么 (k - t) // n 就是每个数字平摊到的操作次数。不妨设 divmod(k - t, n) = q, r。
先看剩下的零头 r（0 ≤ r < n）。只需要对目前 nums 中最小的 r 个数字，分别乘以 multiplier 一次即可。可以用大小为 r 的最大堆找出最小的 r 个数字，时间为 n log r = O(n log n)。
需要注意取模之后再比较大小就没意义了，所以在确定好最小的 r 个数字之前，不要取模。因为
nums中所有值都不超过top，也就不需要取模。
然后给 nums 中每个数字都乘以 multiplier 的 q 次方。注意到这里的 q 依然非常大，需要使用二分法进行幂运算，时间复杂度可以降到 O(log q) = O(log k - log n) ≈ O(log k)。
二分法幂运算在 935. Knight Dialer 和 70. Climbing Stairs 都有涉及（矩阵的幂运算跟整数的幂运算没有本质区别）。在这两题中计算幂用的是正向的循环，如：
MOD = 1_000_000_007
def bi_power(a: int, n: int) -> int:
"""Calculates x ** n % MOD."""
if n == 0: return 1
mask = 1
n1 = n
while n1 := n1 >> 1:
mask <<= 1
res = a
while mask := mask >> 1:
res = res * res % MOD
if n & mask:
res = res * a % MOD
return res还有另外一种计算方式，本题用的是这种方式：
MOD = 1_000_000_007
def bi_power(a: int, n: int) -> int:
"""Calculates x ** n % MOD."""
res = 1
while n > 0:
if n & 1:
res = res * a % MOD
n >>= 1
a = a * a % MOD
return res至此就计算完成了，把当前的 nums 返回即可。时间复杂度 O((n log n) + (log k))，空间复杂度 O(n)。
Normal “k”
上边的处理的基础是 k 足够大，足够把 nums 所有数字都增大到刚好不超过 top。但如果 k 没有那么大，就还是按照 3264. Final Array State After K Multiplication Operations I 中那样，用最小堆来处理。
时间复杂度 O((n + k) log n)，空间复杂度 O(n)。
一个小的优化是类似 1760. Minimum Limit of Balls in a Bag 里的处理，取当前最小值 a，看第二小的值 b，直接对 a 操作若干次使它刚好超过 b。令 p = ⌈log(b + 1 - a, multiplier)⌉，如果剩余的次数足够，那就给 a 加上 multiplier 的 p 次方，再放回堆中。
注意需要保证对于相同的两个数，要优先对在 nums 中排在前边的数字操作。所以如果 b 的下标小于 a 的下标，就令 p = ⌈log(b - a), multiplier⌉，确保 a 不会超过 b。
另外考虑到 Python 的 log 浮点误差问题，虽然没有实际遇到 log 结果上取整有错，但保险起见还是可以特殊处理一下：
def clog(a: int, b: int) -> int:
"""Calculates ceil(log(a, b))."""
p = ceil(log10(a) / log10(b))
if b ** (p - 1) > a:
p -= 1
return p另外注意取模之后再排序就无效了，所以运算过程中不能取模。但进入这个处理逻辑的前提是 k 不够把 nums 所有数字都增大到刚好不超过 top，也就不用取模。
Code
from heapq import heapify, heappop, heappush, heappushpop
from math import ceil, log10
MOD = 1_000_000_007
# def bi_power(a: int, n: int) -> int:
# """Calculates x ** n % MOD."""
# if n == 0: return 1
# mask = 1
# n1 = n
# while n1 := n1 >> 1:
# mask <<= 1
# res = a
# while mask := mask >> 1:
# res = res * res % MOD
# if n & mask:
# res = res * a % MOD
# return res
def bi_power(a: int, n: int) -> int:
"""Calculates x ** n % MOD."""
res = 1
while n > 0:
if n & 1:
res = res * a % MOD
n >>= 1
a = a * a % MOD
return res
def ilog(a: int, b: int) -> int:
"""Calculates int(log(a, b))."""
p = int(log10(a) / log10(b))
if b ** (p + 1) <= a:
p += 1
return p
def clog(a: int, b: int) -> int:
"""Calculates ceil(log(a, b))."""
p = ceil(log10(a) / log10(b))
if b ** (p - 1) > a:
p -= 1
return p
class Solution:
def getFinalState(self, nums: list[int], k: int, multiplier: int) -> list[int]:
if multiplier == 1: return nums
n = len(nums)
top = max(nums)
powers: dict[int, int] = {} # i: ilog(top / nums[i], multiplier)
t = 0
for i in range(n):
p = ilog(top / nums[i], multiplier)
if p == 0: continue
t += p
if t > k: break
powers[i] = p
else:
share, k = divmod(k - t, n)
for i, p in powers.items():
nums[i] *= multiplier ** p
if k > 0:
heap = [(-nums[i], -i) for i in range(k)] # A max-heap to get the minimal k values.
heapify(heap)
for i in range(k, n):
heappushpop(heap, (-nums[i], -i))
for _, i in heap:
nums[-i] = nums[-i] * multiplier % MOD
if share > 0:
tmp = bi_power(multiplier, share)
for i in range(n):
nums[i] = nums[i] * tmp % MOD
return nums
heap = [(v, i) for i, v in enumerate(nums)]
heapify(heap)
while k > 0:
a, i = heappop(heap)
b, j = heap[0]
if j > i: b += 1
p = clog(b / a, multiplier)
if p > k:
p = k
a *= multiplier ** p
k -= p
heappush(heap, (a, i))
result = [0] * n
for v, i in heap:
result[i] = v % MOD
return result
评论需要 JavaScript。