2025-04-01：K 次乘运算后的最终数组Ⅰ。用go语言，给定一个整数数组 nums、一个整数 k 和一个乘数 multip

福大大架构师每日一题

发布于 2025-03-31 19:45:59

2200

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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

解释：

操作	结果
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]

题目来自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 {
    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)
}

Python完整代码如下：

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

import heapq

defquick_mul(x, y, m):
    res = 1
    while y > 0:
        if y & 1:  
            res = (res * x) % m
        y >>= 1
        x = (x * x) % m
    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, i) for i, num inenumerate(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 inrange(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)