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.
1function topKFrequent(nums, k) {
2 const freqMap = {};
3 for (const num of nums) {
4 freqMap[num] = (freqMap[num] || 0) + 1;
5 }
6
7 const minHeap = Object.keys(freqMap).sort((a, b) => freqMap[b] - freqMap[a]).slice(0, k);
8
9 return minHeap.map(Number);
10}
11
12const nums = [1, 1, 1, 2, 2, 3];
13const k = 2;
14console.log(topKFrequent(nums, k));
15We use an object to count frequencies, sort keys by frequency, and take the top k.
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.