LeetCode 3264: Final Array State After K Multiplication Operations I (Min-Heap Simulation with Stable Tie-Break)
LeetCode 3264HeapSimulationToday we solve LeetCode 3264 - Final Array State After K Multiplication Operations I.
Source: https://leetcode.com/problems/final-array-state-after-k-multiplication-operations-i/
English
Problem Summary
You are given an array nums, an integer k, and a multiplier. Repeat exactly k times:
- Pick the minimum value in the current array (if tied, pick the smallest index).
- Replace that value with value * multiplier.
Return the final array after all operations.
Key Insight
Each step needs the current minimum with stable tie-break by index, so a min-heap of pairs (value, index) is the natural fit.
Algorithm
- Build a min-heap with all pairs (nums[i], i).
- Repeat k times: pop the top pair, multiply its value, write back to nums[index], and push updated pair.
- Return nums.
Complexity Analysis
Time: O((n + k) log n).
Space: O(n).
Common Pitfalls
- Forgetting tie-break by index when values are equal.
- Updating the heap value but forgetting to update nums[index].
- Using unstable ordering in custom comparators.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int[] getFinalState(int[] nums, int k, int multiplier) {
PriorityQueue pq = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
return Integer.compare(a[1], b[1]);
});
for (int i = 0; i < nums.length; i++) {
pq.offer(new int[]{nums[i], i});
}
while (k-- > 0) {
int[] cur = pq.poll();
int value = cur[0], idx = cur[1];
value *= multiplier;
nums[idx] = value;
pq.offer(new int[]{value, idx});
}
return nums;
}
} import "container/heap"
type Node struct {
val int
idx int
}
type MinHeap []Node
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
if h[i].val != h[j].val {
return h[i].val < h[j].val
}
return h[i].idx < h[j].idx
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) { *h = append(*h, x.(Node)) }
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func getFinalState(nums []int, k int, multiplier int) []int {
h := &MinHeap{}
heap.Init(h)
for i, v := range nums {
heap.Push(h, Node{val: v, idx: i})
}
for ; k > 0; k-- {
cur := heap.Pop(h).(Node)
cur.val *= multiplier
nums[cur.idx] = cur.val
heap.Push(h, cur)
}
return nums
}class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
using P = pair<int, int>;
auto cmp = [](const P& a, const P& b) {
if (a.first != b.first) return a.first > b.first;
return a.second > b.second;
};
priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);
for (int i = 0; i < (int)nums.size(); i++) {
pq.push({nums[i], i});
}
while (k--) {
auto [value, idx] = pq.top();
pq.pop();
value *= multiplier;
nums[idx] = value;
pq.push({value, idx});
}
return nums;
}
};import heapq
from typing import List
class Solution:
def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
heap = [(v, i) for i, v in enumerate(nums)]
heapq.heapify(heap)
for _ in range(k):
v, i = heapq.heappop(heap)
v *= multiplier
nums[i] = v
heapq.heappush(heap, (v, i))
return numsclass MinHeap {
constructor() { this.data = []; }
less(a, b) {
if (a[0] !== b[0]) return a[0] < b[0];
return a[1] < b[1];
}
push(x) {
const d = this.data;
d.push(x);
let i = d.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.less(d[p], d[i])) break;
[d[p], d[i]] = [d[i], d[p]];
i = p;
}
}
pop() {
const d = this.data;
const top = d[0];
const last = d.pop();
if (d.length) {
d[0] = last;
let i = 0;
while (true) {
let l = i * 2 + 1, r = i * 2 + 2, m = i;
if (l < d.length && !this.less(d[m], d[l])) m = l;
if (r < d.length && !this.less(d[m], d[r])) m = r;
if (m === i) break;
[d[i], d[m]] = [d[m], d[i]];
i = m;
}
}
return top;
}
}
var getFinalState = function(nums, k, multiplier) {
const heap = new MinHeap();
for (let i = 0; i < nums.length; i++) heap.push([nums[i], i]);
while (k-- > 0) {
let [v, i] = heap.pop();
v *= multiplier;
nums[i] = v;
heap.push([v, i]);
}
return nums;
};中文
题目概述
给你数组 nums、整数 k 和 multiplier。执行恰好 k 次操作：
- 每次选择当前数组中的最小值（若有并列，选下标更小的那个）。
- 将该元素替换为 value * multiplier。
返回最终数组。
核心思路
每一步都要快速拿到“值最小、下标最小”的元素，最合适的数据结构是小根堆，堆元素为 (value, index)。
算法步骤
- 初始化小根堆：把每个 (nums[i], i) 放进去。
- 循环 k 次：弹出堆顶，值乘上 multiplier，写回 nums[index]，再把更新后的二元组压回堆。
- 返回 nums。
复杂度分析
时间复杂度：O((n + k) log n)。
空间复杂度：O(n)。
常见陷阱
- 忽略“值相同按下标更小优先”的规则。
- 只更新堆不更新原数组 nums。
- 比较器不稳定导致并列顺序错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int[] getFinalState(int[] nums, int k, int multiplier) {
PriorityQueue pq = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
return Integer.compare(a[1], b[1]);
});
for (int i = 0; i < nums.length; i++) {
pq.offer(new int[]{nums[i], i});
}
while (k-- > 0) {
int[] cur = pq.poll();
int value = cur[0], idx = cur[1];
value *= multiplier;
nums[idx] = value;
pq.offer(new int[]{value, idx});
}
return nums;
}
} import "container/heap"
type Node struct {
val int
idx int
}
type MinHeap []Node
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
if h[i].val != h[j].val {
return h[i].val < h[j].val
}
return h[i].idx < h[j].idx
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) { *h = append(*h, x.(Node)) }
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func getFinalState(nums []int, k int, multiplier int) []int {
h := &MinHeap{}
heap.Init(h)
for i, v := range nums {
heap.Push(h, Node{val: v, idx: i})
}
for ; k > 0; k-- {
cur := heap.Pop(h).(Node)
cur.val *= multiplier
nums[cur.idx] = cur.val
heap.Push(h, cur)
}
return nums
}class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
using P = pair<int, int>;
auto cmp = [](const P& a, const P& b) {
if (a.first != b.first) return a.first > b.first;
return a.second > b.second;
};
priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);
for (int i = 0; i < (int)nums.size(); i++) {
pq.push({nums[i], i});
}
while (k--) {
auto [value, idx] = pq.top();
pq.pop();
value *= multiplier;
nums[idx] = value;
pq.push({value, idx});
}
return nums;
}
};import heapq
from typing import List
class Solution:
def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
heap = [(v, i) for i, v in enumerate(nums)]
heapq.heapify(heap)
for _ in range(k):
v, i = heapq.heappop(heap)
v *= multiplier
nums[i] = v
heapq.heappush(heap, (v, i))
return numsclass MinHeap {
constructor() { this.data = []; }
less(a, b) {
if (a[0] !== b[0]) return a[0] < b[0];
return a[1] < b[1];
}
push(x) {
const d = this.data;
d.push(x);
let i = d.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.less(d[p], d[i])) break;
[d[p], d[i]] = [d[i], d[p]];
i = p;
}
}
pop() {
const d = this.data;
const top = d[0];
const last = d.pop();
if (d.length) {
d[0] = last;
let i = 0;
while (true) {
let l = i * 2 + 1, r = i * 2 + 2, m = i;
if (l < d.length && !this.less(d[m], d[l])) m = l;
if (r < d.length && !this.less(d[m], d[r])) m = r;
if (m === i) break;
[d[i], d[m]] = [d[m], d[i]];
i = m;
}
}
return top;
}
}
var getFinalState = function(nums, k, multiplier) {
const heap = new MinHeap();
for (let i = 0; i < nums.length; i++) heap.push([nums[i], i]);
while (k-- > 0) {
let [v, i] = heap.pop();
v *= multiplier;
nums[i] = v;
heap.push([v, i]);
}
return nums;
};
Comments