javascript 解法, 执行用时: 26 ms, 内存消耗: 57.2 MB, 提交时间: 2024-12-13 09:25:05

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} multiplier
 * @return {number[]}
 */
var getFinalState = function(nums, k, multiplier) {
    const quickMul = (x, y, m) => {
        let res = BigInt(1);
        while (y > 0n) {
            if (y % 2n === 1n) {
                res = (res * x) % m;
            }
            y >>= 1n;
            x = (x * x) % m;
        }
        return res;
    };

    if (multiplier === 1) {
        return nums;
    }
    const n = nums.length;
    const m = 1000000007;
    let mx = 0;
    const pq = new MinPriorityQueue({
        priority: (a) => a.first * 100000 + a.second
    });
    for (let i = 0; i < n; i++) {
        mx = Math.max(mx, nums[i]);
        pq.enqueue({
            first: nums[i],
            second: i
        });
    }
    for (; pq.front().element.first < mx && k > 0; k--) {
        let x = pq.dequeue().element;
        x.first *= multiplier;
        pq.enqueue(x);
    }
    for (let i = 0; i < n; i++) {
        let x = pq.dequeue().element;
        const t = Math.floor(k / n) + (i < k % n ? 1 : 0);
        nums[x.second] = Number(((BigInt(x.first) % BigInt(m)) * quickMul(BigInt(multiplier), BigInt(t), BigInt(m))) % BigInt(m));
    }
    return nums;
};

rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2024-12-13 09:24:47

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
    fn quick_mul(x: i64, y: i64, m: i64) -> i64 {
        let mut res = 1;
        let mut x = x;
        let mut y = y;
        while y > 0 {
            if y % 2 == 1 {
                res = (res * x) % m;
            }
            x = (x * x) % m;
            y /= 2;
        }
        res
    }

    pub fn get_final_state(nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
        if multiplier == 1 {
            return nums;
        }
        let n = nums.len();
        let m = 1_000_000_007;
        let mx = *nums.iter().max().unwrap() as i64;
        let mut v: BinaryHeap<Reverse<(i64, usize)>> = nums.into_iter()
            .enumerate()
            .map(|(i, num)| Reverse((num as i64, i)))
            .collect();

        let mut k = k as i64;
        while let Some(Reverse((val, _))) = v.peek() {
            if *val >= mx || k == 0 {
                break;
            }
            let Reverse((mut min_val, idx)) = v.pop().unwrap();
            min_val *= multiplier as i64;
            v.push(Reverse((min_val, idx)));
            k -= 1;
        }

        let mut result = vec![0; n];
        let mut vec_v = v.into_vec();
        vec_v.sort_unstable_by_key(|Reverse((val, idx))| (*val, *idx));

        for (i, Reverse((val, idx))) in vec_v.iter().enumerate() {
            let t = k / n as i64 + if (i as i64) < k % n as i64 { 1 } else { 0 };
            result[*idx] = ((val % m) * Solution::quick_mul(multiplier as i64, t, m) % m) as i32;
        }
        result
    }
}

rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2024-12-13 09:24:34

impl Solution {
    // 暴力模拟
    pub fn get_final_state(mut nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
        for _ in 0..k {
            let mut m = 0;
            for j in 1..nums.len() {
                if nums[j] < nums[m] {
                    m = j;
                }
            }
            nums[m] *= multiplier;
        }
        nums
    }
}

golang 解法, 执行用时: 11 ms, 内存消耗: 3.8 MB, 提交时间: 2024-08-26 09:54:20

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}
	}
	heap.Init(&h)

	// 模拟，直到堆顶是 mx
	for ; k > 0 && h[0].x < mx; k-- {
		h[0].x *= multiplier
		heap.Fix(&h, 0)
	}

	// 剩余的操作可以直接用公式计算
	sort.Slice(h, func(i, j int) bool { return less(h[i], h[j]) })
	for i, p := range h {
		e := k / n
		if i < k%n {
			e++
		}
		nums[p.i] = p.x % mod * pow(multiplier, e) % 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
}

cpp 解法, 执行用时: 7 ms, 内存消耗: 26.5 MB, 提交时间: 2024-08-26 09:53:56

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);
        vector<pair<long long, int>> h(n);
        for (int i = 0; i < n; i++) {
            h[i] = {nums[i], i};
        }
        ranges::make_heap(h, greater<>()); // 最小堆，O(n) 堆化

        // 模拟，直到堆顶是 mx
        for (; k && h[0].first < mx; k--) {
            ranges::pop_heap(h, greater<>());
            h.back().first *= multiplier;
            ranges::push_heap(h, greater<>());
        }

        // 剩余的操作可以直接用公式计算
        ranges::sort(h);
        for (int i = 0; i < n; i++) {
            auto& [x, j] = h[i];
            nums[j] = x % MOD * pow(multiplier, k / n + (i < k % n)) % MOD;
        }
        return move(nums);
    }
};

java 解法, 执行用时: 5 ms, 内存消耗: 44 MB, 提交时间: 2024-08-26 09:53:38

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;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
        for (int i = 0; i < n; i++) {
            mx = Math.max(mx, nums[i]);
            pq.offer(new long[]{nums[i], i});
        }

        // 模拟，直到堆顶是 mx
        for (; k > 0 && pq.peek()[0] < mx; k--) {
            long[] p = pq.poll();
            p[0] *= multiplier;
            pq.offer(p);
        }

        // 剩余的操作可以直接用公式计算
        for (int i = 0; i < n; i++) {
            long[] p = pq.poll();
            nums[(int) p[1]] = (int) (p[0] % MOD * pow(multiplier, k / n + (i < k % n ? 1 : 0)) % 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 解法, 执行用时: 39 ms, 内存消耗: 16.6 MB, 提交时间: 2024-08-26 09:53:08

# 也可以模拟到 k 刚好是 n 的倍数时才停止，这样最后无需排序
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)
        h = [(x, i) for i, x in enumerate(nums)]
        heapify(h)

        # 模拟，直到堆顶是 mx
        while k and (h[0][0] < mx or k % n):
            x, i = h[0]
            heapreplace(h, (x * multiplier, i))
            k -= 1

        # 剩余的操作可以直接用公式计算
        for x, j in h:
            nums[j] = x * pow(multiplier, k // n, MOD) % MOD
        return nums

cpp 解法, 执行用时: 8 ms, 内存消耗: 25.6 MB, 提交时间: 2024-08-26 09:52:14

class Solution {
public:
    // 暴力模拟
    vector<int> getFinalState(vector<int> nums, int k, int multiplier) {
        // 循环k次
        for (int i = 0; i < k; ++i) {
            // 找到nums中的最小值，并将其赋值给m
            int m = *min_element(nums.begin(), nums.end());
            // 在nums中找到最小值的位置，并将迭代器it指向该位置
            auto it = find(nums.begin(), nums.end(), m);
            // 计算最小值在nums中的索引，并将其赋值给idx
            int idx = distance(nums.begin(), it);
            // 将nums中索引为idx的元素乘以multiplier
            nums[idx] *= multiplier;
        }
        // 返回处理后的nums向量
        return nums;
    }
};