2025-04-02：K 次乘运算后的最终数组Ⅱ。用go语言，给定一个整数数组 nums，以及两个整数 k 和 multipli

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]。

解释：

操作

结果

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]

题目来自leetcode3266。

解决步骤

1. 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. 1. 初始nums = [2,1,3,5,6]，k = 5，multiplier = 2。

2. 2. 堆初始化：[ (1,1), (2,0), (3,2), (5,3), (6,4) ]，mx = 6。

3. 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 {     returnlen(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) }

# -*-coding:utf-8-*- import heapq defquick_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 defget_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 inenumerate(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 inrange(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)

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。 欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展