[LeetCode] 每日一题 3266. K 次乘运算后的最终数组 II

题目链接

题目描述

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

题解

题目理解

我们需要对数组执行 k 次操作，每次操作从数组中找到最小值，按规则进行替换和处理。核心目标是高效地模拟这些操作，并且通过优化避免无意义的重复计算。

核心思路

1. 最小堆模拟操作：

   • 使用最小堆（优先队列）维护数组元素的值和位置，能够快速找到当前的最小值。

   • 对每次操作，我们从堆中取出最小值，更新它为 x * multiplier，并重新插入堆。

2. 优化操作：

   • 当数组的最大值成为堆中最小值时，后续的操作呈现规律性，不需要手动模拟。

   • 假设剩余的操作次数为 k，我们可以直接计算每个元素最终会被乘以多少次 multiplier。

3. 快速幂计算：

   • 对于一个数被多次乘以 multiplier 的操作，我们使用快速幂算法计算其结果，并对 10^9 + 7 取模，确保效率。

关于什么是快速幂算法，可以看下面这篇内容：

算法流程

1. 初始化最小堆，将数组元素和索引存入堆中

2. 模拟操作，直到 k 次操作完成或堆中最小值达到数组最大值

3. 根据剩余的操作次数 k 和元素位置计算每个元素的最终值

4. 输出数组

代码实现

class Solution {
    static int MOD = 1000000007;

    public int[] getFinalState(int[] nums, int k, int multiplier) {
        // 如果 multiplier 为 1，则所有元素保持不变
        if (multiplier == 1) {
            return nums;
        }

        // 优先队列（最小堆）用于存储数组值及其索引
        PriorityQueue<long[]> queue = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return Long.compare(a[0], b[0]); // 按值排序
            }
            return Long.compare(a[1], b[1]);   // 按索引排序
        });

        int max = -1; // 记录数组的最大值
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            queue.offer(new long[]{nums[i], i});
        }

        // 手动模拟操作，直到 k 次操作完成或堆中最小值达到最大值
        while (k > 0 && queue.peek()[0] < max) {
            long[] temp = queue.poll();
            temp[0] *= multiplier;
            queue.offer(temp);
            k--;
        }

        // 剩余的 k 次操作，计算最终结果
        for (int i = 0; i < nums.length; i++) {
            long[] temp = queue.poll();
            int idx = (int) temp[1];
            long value = temp[0];

            // 计算每个元素剩余的 multiplier 次数
            int additionalOps = k / nums.length + (i < k % nums.length ? 1 : 0);
            nums[idx] = (int) (value % MOD * pow(multiplier, additionalOps) % MOD);
        }

        return nums;
    }

    // 快速幂计算 (a^n) % MOD
    private long pow(long a, int n) {
        long res = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            n /= 2;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：

  • 构建最小堆的时间复杂度为 O(nlogn)。

  • 每次堆操作的复杂度为 O(logn)，最多进行 k 次堆操作，因此堆操作部分的复杂度为 O(klogn)。

  • 快速幂计算的复杂度为 O(logk)。

  • 总时间复杂度为 O((n+k)logn+nlogk)。

• 空间复杂度：

  • 最小堆的空间复杂度为 O(n)。

总结

通过使用最小堆和快速幂优化，我们高效地解决了这个问题，适用于较大的 k 和 nums 数组。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。