This approach uses a hash map to count the frequency of each element. We then use a min-heap to keep track of the top k elements.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
1from collections import Counter
2import heapq
3
4def topKFrequent(nums, k):
5 count = Counter(nums)
6 return heapq.nlargest(k, count.keys(), key=count.get)
7
8if __name__ == '__main__':
9 nums = [1,1,1,2,2,3]
10 k = 2
11 print(topKFrequent(nums, k))
12We use Python's collections.Counter and heapq.nlargest functions to efficiently get the top k frequent elements.
This approach involves using bucket sort where we create buckets for frequency counts and then extract the top k frequent elements.
Time Complexity: O(n + k).
Space Complexity: O(n).
1import java.util.*;
2
3class Solution {
4 public int[] topKFrequent(int[] nums, int k) {
5 Map<Integer, Integer> freqMap = new HashMap<>();
6 for (int num : nums) {
7 freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
8 }
9
10 List<Integer>[] buckets = new List[nums.length + 1];
11 for (int key : freqMap.keySet()) {
12 int frequency = freqMap.get(key);
13 if (buckets[frequency] == null) {
14 buckets[frequency] = new ArrayList<>();
15 }
16 buckets[frequency].add(key);
17 }
18
19 List<Integer> resultList = new ArrayList<>();
20 for (int pos = buckets.length - 1; pos >= 0 && resultList.size() < k; pos--) {
21 if (buckets[pos] != null) {
22 resultList.addAll(buckets[pos]);
23 }
24 }
25
26 int[] result = new int[k];
27 for (int i = 0; i < k; i++) {
28 result[i] = resultList.get(i);
29 }
30 return result;
31 }
32
33 public static void main(String[] args) {
34 Solution sol = new Solution();
35 int[] nums = {1, 1, 1, 2, 2, 3};
36 int k = 2;
37 int[] result = sol.topKFrequent(nums, k);
38 System.out.println(Arrays.toString(result));
39 }
40}
41By clustering elements into frequency buckets, the most frequented elements appear in the last non-empty buckets.