Skip to content

1636. Sort Array by Increasing Frequency 👍

  • Time:
  • Space: 
 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
struct T {
  int num;
  int freq;
};

class Solution {
 public:
  vector<int> frequencySort(vector<int>& nums) {
    vector<int> ans;
    auto compare = [](const T& a, const T& b) {
      return a.freq == b.freq ? a.num < b.num : a.freq > b.freq;
    };
    priority_queue<T, vector<T>, decltype(compare)> heap(compare);
    unordered_map<int, int> count;

    for (const int num : nums)
      ++count[num];

    for (const auto& [num, freq] : count)
      heap.emplace(num, freq);

    while (!heap.empty()) {
      const auto [num, freq] = heap.top();
      heap.pop();
      for (int i = 0; i < freq; ++i)
        ans.push_back(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[] frequencySort(int[] nums) {
    record T(int num, int freq) {}
    int[] ans = new int[nums.length];
    int ansIndex = 0;
    Map<Integer, Integer> count = new HashMap<>();
    Queue<T> heap = new PriorityQueue<>((a, b) //
                                        -> a.freq == b.freq ? Integer.compare(b.num, a.num)
                                                            : Integer.compare(a.freq, b.freq));

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    for (Map.Entry<Integer, Integer> entry : count.entrySet())
      heap.offer(new T(entry.getKey(), entry.getValue()));

    while (!heap.isEmpty()) {
      final int num = heap.peek().num;
      final int freq = heap.poll().freq;
      for (int i = 0; i < freq; ++i)
        ans[ansIndex++] = 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
27
28
from dataclasses import dataclass


@dataclass(frozen=True)
class T:
  num: int
  freq: int

  def __lt__(self, other):
    if self.freq == other.freq:
      return self.num > other.num
    return self.freq < other.freq


class Solution:
  def frequencySort(self, nums: list[int]) -> list[int]:
    ans = []
    heap = []

    for num, freq in collections.Counter(nums).items():
      heapq.heappush(heap, T(num, freq))

    while len(heap) > 0:
      num = heap[0].num
      freq = heapq.heappop(heap).freq
      ans.extend([num] * freq)

    return ans