3264. Final Array State After K Multiplication Operations I
Description
You are given an integer array nums
, an integer k
, and an integer multiplier
.
You need to perform k
operations on nums
. In each operation:
- Find the minimum value
x
innums
. If there are multiple occurrences of the minimum value, select the one that appears first. - Replace the selected minimum value
x
withx * multiplier
.
Return an integer array denoting the final state of nums
after performing all k
operations.
Example 1:
Input: nums = [2,1,3,5,6], k = 5, multiplier = 2
Output: [8,4,6,5,6]
Explanation:
Operation | Result |
---|---|
After operation 1 | [2, 2, 3, 5, 6] |
After operation 2 | [4, 2, 3, 5, 6] |
After operation 3 | [4, 4, 3, 5, 6] |
After operation 4 | [4, 4, 6, 5, 6] |
After operation 5 | [8, 4, 6, 5, 6] |
Example 2:
Input: nums = [1,2], k = 3, multiplier = 4
Output: [16,8]
Explanation:
Operation | Result |
---|---|
After operation 1 | [4, 2] |
After operation 2 | [4, 8] |
After operation 3 | [16, 8] |
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 10
1 <= multiplier <= 5
Solutions
Solution 1: Priority Queue (Min-Heap) + Simulation
We can use a min-heap to maintain the elements in the array $\textit{nums}$. Each time, we extract the minimum value from the min-heap, multiply it by $\textit{multiplier}$, and then put it back into the min-heap. During the implementation, we insert the indices of the elements into the min-heap and define a custom comparator function to sort the min-heap based on the values of the elements in $\textit{nums}$ as the primary key and the indices as the secondary key.
Finally, we return the array $\textit{nums}$.
The time complexity is $O((n + k) \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
|