西安网站定制开发,网络推广培训课程4万,网站开发费用报价,郑州做网站找赢博科技问题背景
给你一个整数数组 n u m s nums nums#xff0c;一个整数 k k k 和一个整数 m u l t i p l i e r multiplier multiplier。 你需要对 n u m s nums nums 执行 k k k 次操作#xff0c;每次操作中#xff1a;
找到 n u m s nums nums 中的 最小 值 x x x一个整数 k k k 和一个整数 m u l t i p l i e r multiplier multiplier。 你需要对 n u m s nums nums 执行 k k k 次操作每次操作中
找到 n u m s nums nums 中的 最小 值 x x x如果存在多个最小值选择最 前面 的一个。将 x x x 替换为 x × m u l t i p l i e r x \times multiplier x×multiplier。
请你返回执行完 k k k 次乘运算之后最终的 n u m s nums nums 数组。
数据约束 1 ≤ n u m s . l e n g t h ≤ 1 0 4 1 \le nums.length \le 10 ^ 4 1≤nums.length≤104 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \le nums[i] \le 10 ^ 9 1≤nums[i]≤109 1 ≤ k ≤ 1 0 9 1 \le k \le 10 ^ 9 1≤k≤109 1 ≤ m u l t i p l i e r ≤ 1 0 6 1 \le multiplier \le 10 ^ 6 1≤multiplier≤106
解题过程
题干和昨天一样但是数据规模大了很多暴力解一定会超时。 一般的做法 已经分析过了算法上的重点还是堆模拟和 快速幂。
具体实现
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;// 用最小堆来模拟操作其中存储数组中每个元素和它的下标Queuelong[] 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;}
}
