列表

详情


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

给你一个整数数组 nums ,一个整数 k  和一个整数 multiplier 。

你需要对 nums 执行 k 次操作,每次操作中:

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]

 

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> getFinalState(vector<int>& nums, int k, int multiplier) { } };

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
}

上一题