2025-04-02：K 次乘運(yùn)算后的最終數(shù)組Ⅱ。用go語(yǔ)言，給定一個(gè)整數(shù)數(shù)組 nums，以及兩個(gè)整數(shù) k 和 multiplier。你需要對(duì) nums 數(shù)組進(jìn)行 k 次操作。每次操作的流程如下：
1.找到 nums 中的最小值 x，若有多個(gè)最小值則選擇最早出現(xiàn)的那一個(gè)。
2.用 multiplier 乘以 x，然后將其替換掉原來(lái)的 x。
完成 k 次這樣的操作后，對(duì) nums 數(shù)組中的每個(gè)元素進(jìn)行模 1000000007 的運(yùn)算。
最后，返回處理后的 nums 數(shù)組。
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]。
解釋：
操作
結(jié)果
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]
題目來(lái)自leetcode3266。
解決步驟
1.初始檢查：
? 如果
multiplier == 1，那么每次操作不會(huì)改變nums的值，直接返回nums。? 否則，進(jìn)入正常處理流程。
2.初始化優(yōu)先隊(duì)列（最小堆）：
? 將
nums中的每個(gè)元素及其原始索引存入一個(gè)最小堆中。堆的比較規(guī)則是：首先比較值，值小的優(yōu)先；如果值相同，則索引小的優(yōu)先。? 同時(shí)，記錄
nums中的最大值mx。
3.執(zhí)行前k次操作：
? 只要堆頂元素的值小于
mx且k > 0，就執(zhí)行以下操作：? 彈出堆頂元素
x（當(dāng)前最小值）。? 將
x的值乘以multiplier。? 將更新后的
x重新放回堆中。?
k減 1。
? 這一步的目的是盡可能多地讓堆中的元素增長(zhǎng)到至少
mx的值。這樣可以避免在后續(xù)處理中頻繁操作堆。
4.處理剩余的k次操作：
? 如果
k仍然大于 0，說(shuō)明所有元素都已經(jīng)至少是mx的值。此時(shí)，剩余的k次操作可以均勻分配到每個(gè)元素上。? 將堆中的元素按原始索引排序，以便后續(xù)分配操作。
? 對(duì)于堆中的每個(gè)元素，計(jì)算它需要額外進(jìn)行的乘法次數(shù)：
? 總共有
k次操作，n個(gè)元素。? 每個(gè)元素至少進(jìn)行
t = k / n次乘法。? 前
k % n個(gè)元素會(huì)額外進(jìn)行一次乘法。
? 對(duì)于每個(gè)元素，其最終值為
(current_value * (multiplier^t)) % 1000000007，其中t是該元素的乘法次數(shù)。
5.構(gòu)建結(jié)果數(shù)組：
? 根據(jù)堆中元素的原始索引和計(jì)算出的最終值，填充結(jié)果數(shù)組
nums。
?時(shí)間復(fù)雜度：
? 初始化堆：
O(n)（如果使用堆化操作）。? 前
k次操作：每次堆操作是O(log n)，最多進(jìn)行min(k, n log (mx))次操作（因?yàn)槊看尾僮髦辽僮屢粋€(gè)元素翻倍，最多log(mx)次）。? 排序堆：
O(n log n)。? 計(jì)算快速冪：每個(gè)元素最多計(jì)算
O(log k)次（因?yàn)?code>t可以是k/n）。? 總體時(shí)間復(fù)雜度：
O(n log n + min(k, n log mx) log n + n log k)。
?空間復(fù)雜度：
? 堆的存儲(chǔ)：
O(n)。? 其他臨時(shí)變量：
O(1)。? 總體空間復(fù)雜度：
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. 此時(shí)k = 0，無(wú)需進(jìn)一步操作。
5. 按原始索引排序堆：[ (4,1), (5,3), (6,2), (6,4), (8,0) ]。
6. 填充結(jié)果數(shù)組：
?
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 = [] # 使用最小堆存儲(chǔ)元組 (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 # 將堆中的元素按數(shù)值和原始索引排序 sorted_heap = sorted(min_heap, key=lambda x: (x[0], x[1])) # 更新原數(shù)組的值 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 語(yǔ)言和算法為普通開(kāi)發(fā)者提供了強(qiáng)有力的“面試?yán)鳌保⒅铝τ诜窒砣娴木幊讨R(shí)。在這里，您可以找到最新的 Go 語(yǔ)言教程、算法解析、提升面試競(jìng)爭(zhēng)力的秘籍以及行業(yè)動(dòng)態(tài)。 歡迎關(guān)注“福大大架構(gòu)師每日一題”，讓 Go 語(yǔ)言和算法助力您的職業(yè)發(fā)展
熱門(mén)跟貼