class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
}
};
3266. K 次乘运算后的最终数组 II
给你一个整数数组 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
原站题解
cpp 解法, 执行用时: 40 ms, 内存消耗: 51.1 MB, 提交时间: 2024-08-26 09:57:31
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); // 打表,计算出最小的 e 满足 multiplier^e >= 2^i vector<pair<int, long long>> e_pow_m; long long pow_m = 1; int e = 0; for (int pow2 = 1; pow2 <= mx; pow2 <<= 1) { if (pow_m < pow2) { // 由于 multiplier >= 2,这里只需写 if 而不是 while pow_m *= multiplier; e++; } e_pow_m.emplace_back(e, pow_m); } vector<pair<long long, int>> h(n); for (int i = 0; i < n; i++) { h[i] = {nums[i], i}; } auto clone = h; // 把每个数都操作到 >= mx int left = k; int mx_clz = __builtin_clz(mx); for (int i = 0; i < n && left >= 0; i++) { auto [e, pow_m] = e_pow_m[__builtin_clz(nums[i]) - mx_clz]; long long x = nums[i]; if (pow_m / multiplier * x >= mx) { // 多操作了一次 pow_m /= multiplier; e--; } else if (x * pow_m < mx) { // 少操作了一次 pow_m *= multiplier; e++; } left -= e; h[i].first *= pow_m; } if (left < 0) { // 暴力模拟 h = move(clone); ranges::make_heap(h, greater<>()); // 最小堆,O(n) 堆化 while (k--) { ranges::pop_heap(h, greater<>()); h.back().first *= multiplier; ranges::push_heap(h, greater<>()); } for (auto& [x, j] : h) { nums[j] = x % MOD; } return move(nums); } // 剩余的操作可以直接用公式计算 k = left; long long pow1 = pow(multiplier, k / n); long long pow2 = pow1 * multiplier % MOD; // ranges::sort(h) 换成快速选择 ranges::nth_element(h, h.begin() + k % n); for (int i = 0; i < n; i++) { auto& [x, j] = h[i]; nums[j] = x % MOD * (i < k % n ? pow2 : pow1) % MOD; } return move(nums); } };
java 解法, 执行用时: 29 ms, 内存消耗: 45.7 MB, 提交时间: 2024-08-26 09:57:12
class Solution { private static final int MOD = 1_000_000_007; public int[] getFinalState(int[] nums, int k, int multiplier) { if (multiplier == 1) { // 数组不变 return nums; } int n = nums.length; int mx = 0; for (int x : nums) { mx = Math.max(mx, x); } // 打表,计算出最小的 exp 满足 multiplier^exp >= 2^i int mxLZ = Integer.numberOfLeadingZeros(mx); int mxLen = Integer.SIZE - mxLZ; long[] powMs = new long[mxLen]; int[] exps = new int[mxLen]; int exp = 0, m = 0; for (long pow2 = 1, powM = 1; pow2 <= mx; pow2 <<= 1) { if (powM < pow2) { // 由于 multiplier >= 2,这里只需写 if 而不是 while powM *= multiplier; exp++; } powMs[m] = powM; exps[m++] = exp; } // 把每个数都操作到 >= mx long[] a = new long[n]; int left = k; for (int i = 0; i < n && left >= 0; i++) { int j = Integer.numberOfLeadingZeros(nums[i]) - mxLZ; long x = nums[i]; long powM = powMs[j]; int e = exps[j]; if (powM / multiplier * x >= mx) { // 多操作了一次 powM /= multiplier; e--; } else if (x * powM < mx) { // 少操作了一次 powM *= multiplier; e++; } left -= e; a[i] = x * powM; } if (left < 0) { // 暴力模拟 PriorityQueue<long[]> pq = new PriorityQueue<>((p, q) -> p[0] != q[0] ? Long.compare(p[0], q[0]) : Long.compare(p[1], q[1])); for (int i = 0; i < n; i++) { pq.offer(new long[]{nums[i], i}); } while (k-- > 0) { long[] p = pq.poll(); p[0] *= multiplier; pq.offer(p); } while (!pq.isEmpty()) { long[] p = pq.poll(); nums[(int) p[1]] = (int) (p[0] % MOD); } return nums; } Integer[] ids = new Integer[n]; Arrays.setAll(ids, i -> i); Arrays.sort(ids, (i, j) -> Long.compare(a[i], a[j])); // 剩余的操作可以直接用公式计算 k = left; long pow1 = pow(multiplier, k / n); long pow2 = pow1 * multiplier % MOD; for (int i = 0; i < n; i++) { int j = ids[i]; nums[j] = (int) (a[j] % MOD * (i < k % n ? pow2 : pow1) % MOD); } return nums; } private long pow(long x, int n) { long res = 1; for (; n > 0; n /= 2) { if (n % 2 > 0) { res = res * x % MOD; } x = x * x % MOD; } return res; } }
python3 解法, 执行用时: 135 ms, 内存消耗: 19.5 MB, 提交时间: 2024-08-26 09:56:54
class Solution: def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]: if multiplier == 1: # 数组不变 return nums MOD = 1_000_000_007 n = len(nums) mx = max(nums) # 打表,计算出最小的 e 满足 multiplier^e >= 2^i e_pow_m = [] pow_m = pow2 = 1 e = 0 while pow2 <= mx: if pow_m < pow2: # 由于 multiplier >= 2,这里只需写 if 而不是 while pow_m *= multiplier e += 1 e_pow_m.append((e, pow_m)) pow2 <<= 1 # 把每个数都操作到 >= mx left = k clone = nums.copy() mx_len = mx.bit_length() for i, x in enumerate(nums): e, pow_m = e_pow_m[mx_len - x.bit_length()] if pow_m // multiplier * x >= mx: # 多操作了一次 pow_m //= multiplier e -= 1 elif x * pow_m < mx: # 少操作了一次 pow_m *= multiplier e += 1 left -= e if left < 0: break nums[i] *= pow_m if left < 0: # 暴力模拟 h = [(x, i) for i, x in enumerate(clone)] heapify(h) for _ in range(k): x, i = h[0] heapreplace(h, (x * multiplier, i)) for x, j in h: clone[j] = x % MOD return clone # 剩余的操作可以直接用公式计算 k = left pow1 = pow(multiplier, k // n, MOD) pow2 = pow1 * multiplier % MOD for i, (x, j) in enumerate(sorted((x, i) for i, x in enumerate(nums))): nums[j] = x * (pow2 if i < k % n else pow1) % MOD return nums
golang 解法, 执行用时: 60 ms, 内存消耗: 6.9 MB, 提交时间: 2024-08-26 09:56:35
const mod = 1_000_000_007 func getFinalState(nums []int, k int, multiplier int) []int { if multiplier == 1 { // 数组不变 return nums } n := len(nums) mx := 0 h := make(hp, n) for i, x := range nums { mx = max(mx, x) h[i] = pair{x, i} } clone := slices.Clone(h) // 打表,计算出最小的 e 满足 multiplier^e >= 2^i mxLen := bits.Len(uint(mx)) type ep struct{ e, powM int } ePowM := make([]ep, 0, mxLen) for pow2, powM, e := 1, 1, 0; pow2 <= mx; pow2 <<= 1 { if powM < pow2 { // 由于 multiplier >= 2,这里只需写 if 而不是 for powM *= multiplier e++ } ePowM = append(ePowM, ep{e, powM}) } // 把每个数都操作到 >= mx left := k for i := range h { x := h[i].x p := ePowM[mxLen-bits.Len(uint(x))] e, powM := p.e, p.powM if powM/multiplier*x >= mx { // 多操作了一次 powM /= multiplier e-- } else if x*powM < mx { // 少操作了一次 powM *= multiplier e++ } left -= e if left < 0 { break } h[i].x *= powM } if left < 0 { // 暴力模拟 h = clone heap.Init(&h) for ; k > 0; k-- { h[0].x *= multiplier heap.Fix(&h, 0) } sort.Slice(h, func(i, j int) bool { return less(h[i], h[j]) }) for _, p := range h { nums[p.i] = p.x % mod } return nums } // 剩余的操作可以直接用公式计算 k = left pow1 := pow(multiplier, k/n) pow2 := pow1 * multiplier % mod sort.Slice(h, func(i, j int) bool { return less(h[i], h[j]) }) for i, p := range h { pw := pow1 if i < k%n { pw = pow2 } nums[p.i] = p.x % mod * pw % mod } return nums } type pair struct{ x, i int } func less(a, b pair) bool { return a.x < b.x || a.x == b.x && a.i < b.i } type hp []pair func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { return less(h[i], h[j]) } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (hp) Push(any) {} func (hp) Pop() (_ any) { return } func pow(x, n int) int { res := 1 for ; n > 0; n /= 2 { if n%2 > 0 { res = res * x % mod } x = x * x % mod } return res }