【Leetcode 每日一题】3266. K 次乘运算后的最终数组 II

问题背景

给你一个整数数组 $nums$，一个整数 $k$ 和一个整数 $multiplier$。
你需要对 $nums$ 执行 $k$ 次操作，每次操作中：

1. 找到 $nums$ 中的 最小 值 $x$，如果存在多个最小值，选择最 前面 的一个。
2. 将 $x$ 替换为 $x\times multiplier$。

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

数据约束

• $1\le nums.length\le 10^4$
• $1\le nums[i]\le 10^9$
• $1\le k\le 10^9$
• $1\le multiplier\le 10^6$

解题过程

题干和昨天一样，但是数据规模大了很多，暴力解一定会超时。
一般的做法 已经分析过了，算法上的重点还是堆模拟和 快速幂。

具体实现

class Solution {private static final int MOD = 1000000007;public int[] getFinalState(int[] nums, int k, int multiplier) {// 特判乘子为 1 的情形，避免多余的计算if(multiplier == 1) {return nums;}int n = nums.length;int max = 0;// 用最小堆来模拟操作，其中存储数组中每个元素和它的下标Queue<long[]> heap = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? Long.compare(o1[0], o2[0]) : Long.compare(o1[1], o2[1]));for(int i = 0; i < n; i++) {max = Math.max(max, nums[i]);heap.offer(new long[] {nums[i], i});}// 达到统一处理的条件之前，先进行若干次操作，更新堆for(; k > 0 && heap.peek()[0] < max; k--) {long[] cur = heap.poll();cur[0] *= multiplier;heap.offer(cur);}// 用快速幂计算结果，根据堆中的元素更新数组for(int i = 0; i < n; i++) {long[] cur = heap.poll();nums[(int) cur[1]] = (int) (cur[0] % MOD * pow(multiplier, k / n + (i < k % n ? 1 : 0)) % MOD);}return nums;}// 快速幂private long pow(long x, int n) {long res = 1;while(n != 0) {if((n & 1) == 1) {res = res * x % MOD;}x = x * x % MOD;n >>>= 1;}return res;}
}