Leetcode3266：K 次乘运算后的最终数组 II

题目描述：

给你一个整数数组 nums ，一个整数 k  和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

• 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
• 将 x 替换为 x * multiplier 。

k 次操作以后，你需要将 nums 中每一个数值对 10^9 + 7 取余。

请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。

代码思路：

解决方案思路

1. 特殊情况处理：如果 multiplier 为 1，则所有元素乘以 1 不变，直接返回原数组。

2. 初始化：

   • n：数组 nums 的长度。
   • p：一个数组，用于记录每个位置的操作次数。
   • q：一个最大堆（优先队列），用于按值的大小存储元素及其索引，以便快速找到当前最大值。
   • mx：当前数列中的最大值。

3. 前 k 次操作：

   • 使用最大堆 q 初始化并找到初始最大值 mx。
   • 执行 k 次操作，每次取出堆顶元素（当前最大值），将其乘以 multiplier 并重新放入堆中，同时更新该位置的操作次数 p[i]。
   • 如果当前取出的最大值等于 mx，则停止循环（因为后续操作不会影响最大值的选择）。

4. 处理剩余操作：

   • 计算剩余操作次数 k 可以均匀分配给每个元素的次数 pa（整除 n）和剩余无法均匀分配的次数 k（取模 n）。
   • 遍历堆中剩余的元素，对每个元素的位置增加 1 次操作（k 次），直到 k 为 0。

5. 计算最终状态：

   • 遍历数组 nums，对于每个元素，根据其位置 i 的操作次数 p[i] 和均匀分配的操作次数 pa，计算其最终值（乘以 multiplier 的相应次幂，并取模 MOD）。
   • 使用自定义的 pow 函数计算幂次，以避免使用标准库中的 pow 函数可能带来的浮点数精度问题。

6. 返回结果：返回经过所有操作后的最终数列。

自定义 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; // 返回最终结果
    }
};