Skip to content

3264. Final Array State After K Multiplication Operations I 👍

  • Time: $O(n + k\log n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
    vector<int> ans(nums.size());
    using P = pair<int, int>;  // (nums[i], i)
    priority_queue<P, vector<P>, greater<>> minHeap;

    for (int i = 0; i < nums.size(); ++i)
      minHeap.emplace(nums[i], i);

    while (k-- > 0) {
      const auto [num, i] = minHeap.top();
      minHeap.pop();
      minHeap.emplace(num * multiplier, i);
    }

    while (!minHeap.empty()) {
      const auto [num, i] = minHeap.top();
      minHeap.pop();
      ans[i] = num;
    }

    return ans;
  }
};

 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
class Solution {
  public int[] getFinalState(int[] nums, int k, int multiplier) {
    int[] ans = new int[nums.length];
    // (nums[i], i)
    Queue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(
        new PriorityQueue<>(Comparator.comparingInt(Pair<Integer, Integer>::getKey)
                                .thenComparingInt(Pair<Integer, Integer>::getValue)));

    for (int i = 0; i < nums.length; ++i)
      minHeap.offer(new Pair<>(nums[i], i));

    while (k-- > 0) {
      final int num = minHeap.peek().getKey();
      final int i = minHeap.poll().getValue();
      minHeap.offer(new Pair<>(num * multiplier, i));
    }

    while (!minHeap.isEmpty()) {
      final int num = minHeap.peek().getKey();
      final int i = minHeap.poll().getValue();
      ans[i] = num;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def getFinalState(
      self,
      nums: list[int],
      k: int,
      multiplier: int
  ) -> list[int]:
    ans = [0] * len(nums)
    minHeap = [(num, i) for i, num in enumerate(nums)]
    heapq.heapify(minHeap)

    for _ in range(k):
      num, i = heapq.heappop(minHeap)
      heapq.heappush(minHeap, (num * multiplier, i))

    for num, i in minHeap:
      ans[i] = num

    return ans