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.
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 return freqMap.OrderByDescending(x => x.Value).Take(k).Select(x => x.Key).ToArray();
15 }
16
17 public static void Main(string[] args) {
18 int[] nums = new int[] {1, 1, 1, 2, 2, 3};
19 int k = 2;
20 Solution sol = new Solution();
21 int[] result = sol.TopKFrequent(nums, k);
22 Console.WriteLine(string.Join(", ", result));
23 }
24}
25We use a dictionary to count frequencies, then order by descending frequency and take the top k 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).
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8vector<int> topKFrequent(vector<int>& nums, int k) {
9 unordered_map<int, int> freqMap;
10 vector<vector<int>> buckets(nums.size() + 1);
11
12 for (int num : nums) {
13 freqMap[num]++;
14 }
15
16 for (auto& p : freqMap) {
17 buckets[p.second].push_back(p.first);
18 }
19
20 vector<int> result;
21 for (int i = buckets.size() - 1; i >= 0 && result.size() < k; --i) {
22 for (int num : buckets[i]) {
23 result.push_back(num);
24 if (result.size() == k) break;
25 }
26 }
27 return result;
28}
29
30int main() {
31 vector<int> nums = {1, 1, 1, 2, 2, 3};
32 int k = 2;
33 vector<int> result = topKFrequent(nums, k);
34 for (int num : result) {
35 cout << num << " ";
36 }
37 return 0;
38}
39Frequency occurrences are placed in buckets. The largest buckets represent the most frequent elements.