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

2024-12-14

题目：

给你一个整数数组 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

优先级队列 + 暴力求乘积

思路：

用优先级队列存储 pair<nums[i], i> ，然后每次出最小的 nums[i]， 乘以 multiplier 在放回堆中

代码：

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        int n = nums.size(), mod = 1e9 + 7;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        for (int i = 0; i < n; i++) {
            pq.push(make_pair(nums[i], i));
        }
        while (k) {
            auto top = pq.top();
            pq.pop();
            k--;
            pq.push(make_pair((top.first * multiplier) % mod, top.second));
        }
        vector<int> ans(n);
        while (!pq.empty()) {
            auto top = pq.top();
            ans[top.second] = top.first;
            pq.pop();
        }
        return ans;
    }
};

最小堆模拟 + 数学优化

思路：

核心观察：对于两个数 x 和 y，如果 x 在 y 左边，且 x ≤ y 以及 x⋅multiplier > y，那么我们会先操作 x，然后操作 y。由于 x⋅multiplier ≤ y⋅multiplier，这意味着下一次一定会操作 x。继续推导下去，后面的操作顺序一定是 y, x, y, x, ⋯

这意味着当两个数接近时，我们会交替操作这两个数，而不会连续操作同一个数。

对于更多的数的情况也同理，当这些数接近时，我们会按照从小到大的顺序依次操作这些数。

那么，首先用最小堆手动模拟操作，直到原数组的最大值 mx 成为这 n 个数的最小值。根据上面的结论，后面的操作就不需要手动模拟了。

设此时还剩下 k 次操作，那么：
	对于前 kmodn 小的数，还可以再操作 ⌊ k / n ⌋ + 1 次。
	其余元素，还可以再操作 ⌊ k / n ⌋ 次。

代码：

class Solution {
    const int MOD = 1'000'000'007;

    long long pow(long long x, int n) {
        long long res = 1;
        for (; n; n /= 2) {
            if (n % 2) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        if (multiplier == 1) { // 数组不变
            return move(nums);
        }

        int n = nums.size();
        int mx = ranges::max(nums);
        vector<pair<long long, int>> h(n);
        for (int i = 0; i < n; i++) {
            h[i] = {nums[i], i};
        }
        ranges::make_heap(h, greater<>()); // 最小堆，O(n) 堆化

        // 模拟，直到堆顶是 mx
        for (; k && h[0].first < mx; k--) {
            ranges::pop_heap(h, greater<>());
            h.back().first *= multiplier;
            ranges::push_heap(h, greater<>());
        }

        // 剩余的操作可以直接用公式计算
        ranges::sort(h);
        for (int i = 0; i < n; i++) {
            auto& [x, j] = h[i];
            nums[j] = x % MOD * pow(multiplier, k / n + (i < k % n)) % MOD;
        }
        return move(nums);
    }
};