3264. Final Array State After K Multiplication Operations I

Posted on Edited on In

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 in nums. If there are multiple occurrences of the minimum value, select the one that appears first .
  • Replace the selected minimum value x with x * multiplier.

Return an integer array denoting the final state of nums after performing all k operations.

Example 1:

1
2
3
Input: nums = [2,1,3,5,6], k = 5, multiplier = 2

Output: [8,4,6,5,6]

Explanation:

OperationResult
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:

1
2
3
Input: nums = [1,2], k = 3, multiplier = 4

Output: [16,8]

Explanation:

OperationResult
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

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>
            pq;
        for (int i = 0; i < nums.size(); i++) {
            pq.push({nums[i], i});
        }
        for (int i = 0; i < k; i++) {
            auto v = pq.top();
            pq.pop();
            pq.push({v[0] * multiplier, v[1]});
        }
        vector<int> res(nums.size());
        while (!pq.empty()) {
            auto v = pq.top();
            pq.pop();
            int idx = v[1], val = v[0];
            res[idx] = val;
        }
        return res;
    }
};