Leetcode3266：K 次乘运算后的最终数组 II
题目描述：
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。
你需要对 nums 执行 k 次操作，每次操作中：
- 找到
nums中的 最小 值x，如果存在多个最小值，选择最 前面 的一个。 - 将
x替换为x * multiplier。
k 次操作以后，你需要将 nums 中每一个数值对 10^9 + 7 取余。
请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。
代码思路：
解决方案思路
-
特殊情况处理：如果
multiplier为 1，则所有元素乘以 1 不变，直接返回原数组。 -
初始化：
n：数组nums的长度。p：一个数组，用于记录每个位置的操作次数。q：一个最大堆（优先队列），用于按值的大小存储元素及其索引，以便快速找到当前最大值。mx：当前数列中的最大值。
-
前
k次操作：- 使用最大堆
q初始化并找到初始最大值mx。 - 执行
k次操作，每次取出堆顶元素（当前最大值），将其乘以multiplier并重新放入堆中，同时更新该位置的操作次数p[i]。 - 如果当前取出的最大值等于
mx，则停止循环（因为后续操作不会影响最大值的选择）。
- 使用最大堆
-
处理剩余操作：
- 计算剩余操作次数
k可以均匀分配给每个元素的次数pa（整除n）和剩余无法均匀分配的次数k（取模n）。 - 遍历堆中剩余的元素，对每个元素的位置增加
1次操作（k次），直到k为 0。
- 计算剩余操作次数
-
计算最终状态：
- 遍历数组
nums，对于每个元素，根据其位置i的操作次数p[i]和均匀分配的操作次数pa，计算其最终值（乘以multiplier的相应次幂，并取模MOD）。 - 使用自定义的
pow函数计算幂次，以避免使用标准库中的pow函数可能带来的浮点数精度问题。
- 遍历数组
-
返回结果：返回经过所有操作后的最终数列。
自定义 pow 函数
- 实现快速幂算法，用于高效计算
x的y次幂并对MOD取模。 - 通过不断将指数
y减半并平方基数x，同时根据y的奇偶性决定是否将当前基数x乘入结果ans中，实现高效的幂次计算。
总结
该代码通过优先队列（最大堆）高效地选择当前最大值，并通过记录每个位置的操作次数和计算幂次，最终得到经过 k 次操作后的数列状态。通过自定义的 pow 函数确保计算过程中不会超出整数范围，并避免使用浮点数运算带来的精度问题。
代码实现：
const int MOD = 1000000007; // 定义一个常量 MOD，用于取模运算，防止整数溢出
class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
if (multiplier == 1) return nums; // 如果 multiplier 为 1，则任何数乘以 1 都不变，直接返回原数组
int n = nums.size(); // 获取数组 nums 的长度
vector<int> p(n); // 初始化一个长度为 n 的数组 p，用于记录每个位置的操作次数
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q; // 定义一个最大堆 q，用于存储元素值及其索引，元素值大的优先级高
int mx = 0; // 初始化最大值 mx 为 0
// 初始化最大堆 q 和找到初始最大值 mx
for (int i = 0; i < n; i++) {
q.push({nums[i], i}); // 将 nums[i] 和其索引 i 作为一对放入最大堆 q
if (nums[i] >= mx) { // 更新最大值 mx
mx = nums[i];
}
}
// 执行 k 次操作
while (k > 0) {
auto [num, i] = q.top(); // 从最大堆 q 中取出当前最大值 num 及其索引 i
q.pop(); // 弹出最大堆 q 的堆顶元素
q.push({num * multiplier, i}); // 将 num 乘以 multiplier 后的结果和索引 i 重新放入最大堆 q
p[i]++; // 增加索引 i 位置的操作次数
k--; // 减少剩余操作次数
// 如果当前取出的最大值等于 mx，则后续操作不会改变最大值的选择，可以提前退出循环
if (num == mx)
break;
}
// 计算剩余操作次数可以均匀分配给每个元素的次数 pa 和剩余次数 k'
int pa = k / n; // 计算每个元素可以均匀分配到的操作次数
k %= n; // 计算剩余无法均匀分配的操作次数
// 处理剩余操作次数 k'
while (k > 0) {
int i = q.top().second; // 从最大堆 q 中取出当前堆顶元素的索引 i（不考虑值，因为此时值可能已变）
q.pop(); // 弹出最大堆 q 的堆顶元素
p[i]++; // 增加索引 i 位置的操作次数
k--; // 减少剩余操作次数
}
// 计算最终状态
for (int i = 0; i < n; i++) {
// nums[i] 乘以 multiplier 的 (p[i] + pa) 次幂，并对 MOD 取模
nums[i] = (nums[i] * pow(multiplier, p[i] + pa)) % MOD;
}
return nums; // 返回经过所有操作后的最终数列
}
// 自定义的 pow 函数，用于计算 x 的 y 次幂并对 MOD 取模
long long pow(long long x, int y) {
long long ans = 1; // 初始化结果为 1
while (y > 0) { // 当 y 大于 0 时循环
if ((y & 1)) { // 如果 y 是奇数
ans = (ans * x) % MOD; // 将 ans 乘以 x 并对 MOD 取模
}
x = (x * x) % MOD; // 将 x 平方并对 MOD 取模
y >>= 1; // y 右移一位，相当于 y 除以 2
}
return ans; // 返回最终结果
}
};