2025-04-01：K 次乘运算后的最终数组Ⅰ。用go语言，给定一个整数数组 nums、一个整数 k 和一个乘数 multiplier。你需要对数组 nums 执行 k 次操作。每次操作的步骤如下：

找到数组中最小的元素 x。如果有多个相同的最小值，则选择第一个出现的那个。

将该最小值 x 用 x * multiplier 替换。

你的任务是返回经过 k 次乘法运算后的最终数组 nums。

1 <= nums.length <= 100。

1 <= nums[i] <= 100。

1 <= k <= 10。

1 <= multiplier <= 5。

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2。

输出：[8,4,6,5,6]。

解释：

题目来自leetcode3264。

大体步骤如下：

1. 初始化：

   • 首先，记录数组的长度 n 和一个大质数 m（在这里是 10^9 + 7，通常用来避免整数溢出）。
   • 创建一个最小堆 v 用于存储数组中的元素和它们的索引，从而能够快速找到当前最小的元素。

2. 构建最小堆：

   • 遍历数组 nums，将每个元素和它的索引放入最小堆 v。
   • 在这个过程中，更新当前数组中的最大值 mx，以便后续判断。

3. 乘法操作：

   • 利用一个循环，在堆顶元素的值小于 mx 并且 k 大于 0 的条件下进行 k 次操作。
   • 每次循环从堆中弹出最小元素 x，将其值乘以 multiplier，再将更新后的元素重新放回堆中。

4. 处理剩余的 k 值：

   • 一旦所有最小值都被乘过 multiplier 或所有操作已完成，接下来需要计算每个元素在经过 k 次操作后的最终结果。
   • 计算每个数组元素应该经历的乘法次数，这个次数是通过 k 除以 n 得到的基本次数 t，然后根据 k 余 n 判断哪些元素还需多乘一次。
   • 最后对每个元素进行相应的乘法操作，利用快速幂算法 quickMul 来优化乘法计算，以保证在大范围内的快速计算并避免溢出。

5. 返回结果：

   • 最后，更新 nums 数组为经过 k 次乘法操作后的最终结果，并将其返回。

时间复杂度

• 构建最小堆：将 n 个元素放入最小堆的时间复杂度为 O(n log n)。在这个过程中，我们需要遍历整个数组。
• 乘法操作：在每次操作中从最小堆中弹出一个元素并插入回去，时间复杂度为 O(log n)，由于最多进行 k 次操作，这部分的复杂度为 O(k log n)。
• 计算最终结果：此步骤需要遍历 n 个元素并进行乘法运算，时间复杂度为 O(n)。

结合上述步骤，总的时间复杂度为：
[ O(n \log n) + O(k \log n) + O(n) = O(n \log n) ]
因为在 n 较大的情况下，O(n log n) 是主导项。

空间复杂度

• 最小堆：存储数组中的所有元素和它们的索引，所需空间为 O(n)。
• 其他变量：几个整数和数组标记等，因此总的额外空间复杂度为 O(n)。

综上所述，时间复杂度为 O(n log n)，空间复杂度为 O(n)。

Go完整代码如下：

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

func quickMul(x, y, m int64) int64 {
	res := int64(1)
	for y > 0 {
		if (y & 1) == 1 {
			res = (res * x) % m
		}
		y >>= 1
		x = (x * x) % m
	}
	return res
}

func getFinalState(nums []int, k int, multiplier int) []int {
	if multiplier == 1 {
		return nums
	}
	n, m := len(nums), int64(1e9+7)
	mx := 0
	var v minHeap
	for i, num := range nums {
		mx = max(mx, num)
		v = append(v, pair{int64(num), i})
	}
	heap.Init(&v)
	for ; v[0].first < int64(mx) && k > 0; k-- {
		x := heap.Pop(&v).(pair)
		x.first *= int64(multiplier)
		heap.Push(&v, x)
	}
	sort.Slice(v, func(i, j int) bool {
		return v[i].first < v[j].first || v[i].first == v[j].first && v[i].second < v[j].second
	})
	for i := 0; i < n; i++ {
		t := k / n
		if i < k%n {
			t++
		}
		nums[v[i].second] = int((v[i].first % m) * quickMul(int64(multiplier), int64(t), m) % m)
	}
	return nums
}

type pair struct {
	first  int64
	second int
}

type minHeap []pair

func (h minHeap) Len() int {
	return len(h)
}
func (h minHeap) Less(i, j int) bool {
	return h[i].first < h[j].first || h[i].first == h[j].first && h[i].second < h[j].second
}
func (h minHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *minHeap) Push(x interface{}) {
	*h = append(*h, x.(pair))
}

func (h *minHeap) Pop() interface{} {
	n := len(*h)
	res := (*h)[n-1]
	*h = (*h)[0 : n-1]
	return res
}

func main() {
	nums := []int{2, 1, 3, 5, 6}
	k := 5
	multiplier := 2
	result := getFinalState(nums, k, multiplier)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import heapq

def quick_mul(x, y, m):
    res = 1
    while y > 0:
        if y & 1:  
            res = (res * x) % m
        y >>= 1
        x = (x * x) % m
    return res

def get_final_state(nums, k, multiplier):
    if multiplier == 1:
        return nums
    
    n = len(nums)
    m = 10**9 + 7
    mx = max(nums)
    min_heap = [(num, i) for i, num in enumerate(nums)]
    heapq.heapify(min_heap)

    while min_heap and min_heap[0][0] < mx and k > 0:
        x = heapq.heappop(min_heap)
        new_value = x[0] * multiplier
        heapq.heappush(min_heap, (new_value, x[1]))
        k -= 1

    min_heap.sort(key=lambda pair: (pair[0], pair[1]))

    for i in range(n):
        t = k // n
        if i < k % n:
            t += 1
        nums[min_heap[i][1]] = (min_heap[i][0] % m) * quick_mul(multiplier, t, m) % m

    return nums

# 测试代码
if __name__ == "__main__":
    nums = [2, 1, 3, 5, 6]
    k = 5
    multiplier = 2
    result = get_final_state(nums, k, multiplier)
    print(result)