Skip to content

347. Top K Frequent Elements 👍

Approach 1: Heap

  • Time: $O(n\log k)$
  • 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
26
27
28
29
struct T {
  int num;
  int freq;
};

class Solution {
 public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    const int n = nums.size();
    vector<int> ans;
    unordered_map<int, int> count;
    auto compare = [](const T& a, const T& b) { return a.freq > b.freq; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);

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

    for (const auto& [num, freq] : count) {
      minHeap.emplace(num, freq);
      if (minHeap.size() > k)
        minHeap.pop();
    }

    while (!minHeap.empty())
      ans.push_back(minHeap.top().num), minHeap.pop();

    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
29
30
31
32
33
class T {
  public int num;
  public int freq;
  public T(int num, int freq) {
    this.num = num;
    this.freq = freq;
  }
}

class Solution {
  public int[] topKFrequent(int[] nums, int k) {
    final int n = nums.length;
    int[] ans = new int[k];
    Map<Integer, Integer> count = new HashMap<>();
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> 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()) {
      final int num = entry.getKey();
      final int freq = entry.getValue();
      minHeap.offer(new T(num, freq));
      if (minHeap.size() > k)
        minHeap.poll();
    }

    for (int i = 0; i < k; ++i)
      ans[i] = minHeap.poll().num;

    return ans;
  }
}

Approach 2: Bucket Sort

  • Time: $O(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
class Solution {
 public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    const int n = nums.size();
    vector<int> ans;
    vector<vector<int>> bucket(n + 1);
    unordered_map<int, int> count;

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

    for (const auto& [num, freq] : count)
      bucket[freq].push_back(num);

    for (int freq = n; freq > 0; --freq) {
      for (const int num : bucket[freq])
        ans.push_back(num);
      if (ans.size() == k)
        return ans;
    }

    throw;
  }
};

 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
class Solution {
  public int[] topKFrequent(int[] nums, int k) {
    final int n = nums.length;
    List<Integer> ans = new ArrayList<>();
    List<Integer>[] bucket = new List[n + 1];
    Map<Integer, Integer> count = new HashMap<>();

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

    for (final int num : count.keySet()) {
      final int freq = count.get(num);
      if (bucket[freq] == null)
        bucket[freq] = new ArrayList<>();
      bucket[freq].add(num);
    }

    for (int freq = n; freq > 0; --freq) {
      if (bucket[freq] != null)
        ans.addAll(bucket[freq]);
      if (ans.size() == k)
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

    throw new IllegalArgumentException();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def topKFrequent(self, nums: list[int], k: int) -> list[int]:
    ans = []
    bucket = [[] for _ in range(len(nums) + 1)]

    for num, freq in collections.Counter(nums).items():
      bucket[freq].append(num)

    for b in reversed(bucket):
      ans += b
      if len(ans) == k:
        return ans