2025-04-02：K 次乘运算后的最终数组Ⅱ。用go语言，给定一个整数数组 nums，以及两个整数 k 和 multiplier。你需要对 nums 数组进行 k 次操作。每次操作的流程如下：

1.找到 nums 中的最小值 x，若有多个最小值则选择最早出现的那一个。

2.用 multiplier 乘以 x，然后将其替换掉原来的 x。

完成 k 次这样的操作后，对 nums 数组中的每个元素进行模 1000000007 的运算。

最后，返回处理后的 nums 数组。

1 <= nums.length <= 10000。

1 <= nums[i] <= 1000000000。

1 <= k <= 1000000000。

1 <= multiplier <= 1000000。

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

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

解释：

题目来自leetcode3266。

解决步骤

1. 初始检查：

   • 如果 multiplier == 1，那么每次操作不会改变 nums 的值，直接返回 nums。
   • 否则，进入正常处理流程。

2. 初始化优先队列（最小堆）：

   • 将 nums 中的每个元素及其原始索引存入一个最小堆中。堆的比较规则是：首先比较值，值小的优先；如果值相同，则索引小的优先。
   • 同时，记录 nums 中的最大值 mx。

3. 执行前 k 次操作：

   • 只要堆顶元素的值小于 mx 且 k > 0，就执行以下操作：
     • 弹出堆顶元素 x（当前最小值）。
     • 将 x 的值乘以 multiplier。
     • 将更新后的 x 重新放回堆中。
     • k 减 1。
   • 这一步的目的是尽可能多地让堆中的元素增长到至少 mx 的值。这样可以避免在后续处理中频繁操作堆。

4. 处理剩余的 k 次操作：

   • 如果 k 仍然大于 0，说明所有元素都已经至少是 mx 的值。此时，剩余的 k 次操作可以均匀分配到每个元素上。
   • 将堆中的元素按原始索引排序，以便后续分配操作。
   • 对于堆中的每个元素，计算它需要额外进行的乘法次数：
     • 总共有 k 次操作，n 个元素。
     • 每个元素至少进行 t = k / n 次乘法。
     • 前 k % n 个元素会额外进行一次乘法。
   • 对于每个元素，其最终值为 (current_value * (multiplier^t)) % 1000000007，其中 t 是该元素的乘法次数。

5. 构建结果数组：

   • 根据堆中元素的原始索引和计算出的最终值，填充结果数组 nums。

时间复杂度和空间复杂度

• 时间复杂度：
  • 初始化堆：O(n)（如果使用堆化操作）。
  • 前 k 次操作：每次堆操作是 O(log n)，最多进行 min(k, n log (mx)) 次操作（因为每次操作至少让一个元素翻倍，最多 log(mx) 次）。
  • 排序堆：O(n log n)。
  • 计算快速幂：每个元素最多计算 O(log k) 次（因为 t 可以是 k/n）。
  • 总体时间复杂度：O(n log n + min(k, n log mx) log n + n log k)。
• 空间复杂度：
  • 堆的存储：O(n)。
  • 其他临时变量：O(1)。
  • 总体空间复杂度：O(n)。

示例的详细过程

1. 初始 nums = [2,1,3,5,6]，k = 5，multiplier = 2。
2. 堆初始化：[ (1,1), (2,0), (3,2), (5,3), (6,4) ]，mx = 6。
3. 前 k 次操作：
   • 弹出 (1,1)，乘以 2 得 (2,1)，放回堆。堆：[ (2,0), (2,1), (3,2), (5,3), (6,4) ]，k = 4。
   • 弹出 (2,0)，乘以 2 得 (4,0)，放回堆。堆：[ (2,1), (3,2), (4,0), (5,3), (6,4) ]，k = 3。
   • 弹出 (2,1)，乘以 2 得 (4,1)，放回堆。堆：[ (3,2), (4,0), (4,1), (5,3), (6,4) ]，k = 2。
   • 弹出 (3,2)，乘以 2 得 (6,2)，放回堆。堆：[ (4,0), (4,1), (5,3), (6,2), (6,4) ]，k = 1。
   • 弹出 (4,0)，乘以 2 得 (8,0)，放回堆。堆：[ (4,1), (5,3), (6,2), (6,4), (8,0) ]，k = 0。
4. 此时 k = 0，无需进一步操作。
5. 按原始索引排序堆：[ (4,1), (5,3), (6,2), (6,4), (8,0) ]。
6. 填充结果数组：
   • nums[1] = 4 % 1000000007 = 4。
   • nums[3] = 5 % 1000000007 = 5。
   • nums[2] = 6 % 1000000007 = 6。
   • nums[4] = 6 % 1000000007 = 6。
   • nums[0] = 8 % 1000000007 = 8。
7. 最终 nums = [8,4,6,5,6]。

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:  # 如果 y 的最低位为 1
            res = (res * x) % m
        y >>= 1  # y 右移一位
        x = (x * x) % m  # x 自身平方并取模
    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, index)
    for index, num in enumerate(nums):
        heapq.heappush(min_heap, (num, index))
    
    # k 次替换操作
    while min_heap[0][0] < mx and k > 0:
        x = heapq.heappop(min_heap)  # 取出最小值
        x_value, x_index = x
        x_value *= multiplier  # 乘以 multiplier
        heapq.heappush(min_heap, (x_value, x_index))  # 将新值重新入堆
        k -= 1
    
    # 将堆中的元素按数值和原始索引排序
    sorted_heap = sorted(min_heap, key=lambda x: (x[0], x[1]))
    
    # 更新原数组的值
    for i in range(n):
        t = k // n
        if i < k % n:
            t += 1
        nums[sorted_heap[i][1]] = (sorted_heap[i][0] % m) * quick_mul(multiplier, t, m) % m
    
    return nums

# 示例
nums = [2, 1, 3, 5, 6]
k = 5
multiplier = 2
result = get_final_state(nums, k, multiplier)
print(result)