3266.K 次乘运算后的最终数组 II
【LetMeFly】3266.K 次乘运算后的最终数组 II:堆(快速幂)
力扣题目链接:https://leetcode.cn/problems/final-array-state-after-k-multiplication-operations-ii/
给你一个整数数组 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 <= 104
1 <= nums[i] <= 109
1 <= k <= 109
1 <= multiplier <= 106
解题方法:堆 + 快速幂
对于两个数$x\lt y$,如果$x\times multiplier\gt y$,那么下次选择将会是$y$,而$y\times multiplier$后又会大于$x\times multiplier$,下下次将会选择的是$x$,然后是$y$,……
也就是说,两个数较为接近后(之间的倍数小于$multiplier$),将会每个数依次被选中。
多个数也一样,假设多个数中最大的数是$M$,当$M$第一次变成最小的数时,其他所有的数都$\geq M$且$\lt M\times multiplier$。也就是说这时候所有的数都会比较接近,所有的数会像前面例子中的$x$和$y$一样依次被选中。
假设此时还剩$k$次操作,那么:
- 前$k% n$小的数还会被执行$\lfloor\frac{k}{n}\rfloor+1$次操作;
- 其余数还会被执行$\lfloor\frac{k}{n}\rfloor$次操作。
对于$M$变成最小数之前的操作,我们可以使用堆或优先队列模拟进行;
对于之后的操作,可以使用快速幂来计算。
时空复杂度分析
- 时间复杂度$O(n\log n\log_mM)$。单个数最多被模拟$\log_m M$次,最多模拟$n$个数,单次模拟时间复杂度$O(\log n)$。
- 空间复杂度$O(n)$
其中$m=multiplier$,$n=len(nums)$,$M=\max(nums)$。
若$m=1$则可立即返回原数组,否则$m$至少为$2$,$M$最大为$10^9$,$n$最大为$10^4$,$\max(n\log n\log_mM)=10^4\times \log 10^4\times \log 10^9$=$10^4\times 13.288\times 29.897=3972713.36\approx4\times 10^6$
这数据范围不错。
AC代码
C++
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/144473973