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).
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
6 public int[] TopKFrequent(int[] nums, int k) {
7 var freqMap = new Dictionary<int, int>();
8 foreach (var num in nums) {
9 if (!freqMap.ContainsKey(num))
10 freqMap[num] = 0;
11 freqMap[num]++;
12 }
13
14 List<int>[] buckets = new List<int>[nums.Length + 1];
15 foreach (var pair in freqMap) {
16 int freq = pair.Value;
17 if (buckets[freq] == null)
18 buckets[freq] = new List<int>();
19 buckets[freq].Add(pair.Key);
20 }
21
22 List<int> res = new List<int>();
23 for (int i = buckets.Length - 1; i >= 0 && res.Count < k; --i) {
24 if (buckets[i] != null)
25 res.AddRange(buckets[i].ToArray());
26 }
27
28 return res.Take(k).ToArray();
29 }
30
31 public static void Main(string[] args) {
32 int[] nums = new int[] {1, 1, 1, 2, 2, 3};
33 int k = 2;
34 Solution sol = new Solution();
35 int[] result = sol.TopKFrequent(nums, k);
36 Console.WriteLine(string.Join(", ", result));
37 }
38}
39In this C# implementation, frequency of elements is handled with lists representing buckets, aiding the direct extraction of frequent elements.