Final Array State After K Multiplication Operations I
EasyArrayMathHeap (Priority Queue)Simulation
Solution
Solution1: Brute Force
function getFinalState(nums: number[], k: number, multiplier: number): number[] {
while (0 < k) {
let [minValue, minIndex] = [Number.MAX_SAFE_INTEGER, -1];
nums.forEach((num, i) => {
if (num < minValue) {
minValue = num;
minIndex = i;
}
});
nums[minIndex] *= multiplier;
k -= 1;
}
return nums;
}
Complexity
- Time:
O(K * N)
- Space:
O(1)
Solution2: Heap
import { Heap } from '@algorithm/lib';
export function getFinalState(nums: number[], k: number, multiplier: number): number[] {
const heap = new Heap<[number, number]>((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));
nums.forEach((num, i) => {
heap.push([num, i]);
});
while (0 < k) {
const [minValue, minIndex] = heap.pop()!;
nums[minIndex] = minValue * multiplier;
heap.push([minValue * multiplier, minIndex]);
k -= 1;
}
return nums;
}
Complexity
- Time:
O(K * logN)
- Space:
O(N)