目标
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。
你需要对 nums 执行 k 次操作，每次操作中：
- 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
- 将 x 替换为 x * multiplier 。
k 次操作以后，你需要将 nums 中每一个数值对 10^9 + 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 <= 10^4
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9
- 1 <= multiplier <= 10^6
思路
有一个数组 nums，我们需要执行 k 次操作，每次操作选择数组中最小元素 min，并将它的值替换为 min * multiplier，返回最终的数组。数据范围比 3264.K次乘运算后的最终数组I 大，multiplier 也大，会溢出，需要进行取余运算。
首先 k 最大 10^9，还沿用昨天模拟的解法会超时。更重要的是，由于乘积很大，我们只能在队列中保存取余后的数据，如果还按找之前模拟来取最小元素就不对了。
我们发现，当执行一些次操作之后，所有元素都会被乘以 multiplier，当 k / n 比较大时，我们可以使用快速幂先计算出 multiplier 的 k/n 幂，然后再与元素相乘。
关键在于何时开始使用上面的思路来计算，考虑 1 2 4 8 16，multiplier 为 2，k 为 20。
2 2 4 8 16
4 2 4 8 16
4 4 4 8 16
8 4 4 8 16
8 8 4 8 16
8 8 8 8 16
16 8 8 8 16
16 16 8 8 16
16 16 16 8 16
16 16 16 16 16
可以发现 当前数组 最小值 乘以 multiplier 大于 原数组 元素的 最大值 时，后面再乘以 multiplier 就是每一个元素执行一次了。
因此我们需要先使用堆模拟前面几次操作，直到满足上面的条件。注意：堆中数据不能取模，满足条件之前堆中数据使用 long 型不会溢出。
代码
/**
* @date 2024-12-14 10:31
*/
public class GetFinalState3266 {
public int[] getFinalState(int[] nums, int k, int multiplier) {
if (multiplier == 1) {
return nums;
}
int mod = 1000000007;
int n = nums.length;
long[] mul = new long[n];
for (int i = 0; i < n; i++) {
mul[i] = nums[i];
}
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
long compare = mul[a] - mul[b];
if (compare != 0) {
return (int) compare;
}
return a - b;
});
long max = 0;
for (int i = 0; i < n; i++) {
q.offer(i);
max = Math.max(max, nums[i]);
}
int i = 0;
for (; i < k; i++) {
if (mul[q.peek()] * (long) multiplier > max) {
break;
}
Integer index = q.poll();
mul[index] = mul[index] * multiplier;
q.offer(index);
}
int remainder = k - i;
if (remainder >= n) {
long pow = pow(multiplier, remainder / n);
for (int j = 0; j < n; j++) {
Integer index = q.poll();
int rem = remainder % n;
mul[index] = (int) ((mul[index] * pow % mod * (j < rem ? (long) multiplier : 1)) % mod);
}
} else {
for (int j = 0; j < remainder; j++) {
Integer index = q.poll();
mul[index] = (int) ((mul[index] * (long) multiplier) % mod);
q.offer(index);
}
}
for (int j = 0; j < n; j++) {
nums[j] = (int) mul[j];
}
return nums;
}
public long pow(long base, int exponent) {
long res = 1;
int mod = 1000000007;
while (exponent > 0) {
if ((exponent & 1) == 1) {
res = res * base % mod;
}
base = base * base % mod;
exponent >>= 1;
}
return res;
}
}
性能
