347. Top K Frequent Elements
Skills:
Bucket Sortmin-heap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Solution 1: MinPriorityQueue
Approach
Map<number, number>Time and space complexity
Solution
1function topKFrequent(nums: number[], k: number): number[] {
2 /**
3 MinPriorityQueue
4 */
5
6 let num_map: Map<number, number> = new Map();
7 for (let i = 0; i < nums.length; i++) {
8 if (!num_map.has(nums[i])) {
9 num_map.set(nums[i], 0)
10 }
11 num_map.set(nums[i], (num_map.get(nums[i]) || 0) + 1)
12 }
13
14 const min_heap = new MinPriorityQueue((entry) => entry.value);
15 for (const [key, value] of num_map.entries()) {
16 min_heap.enqueue({ key, value })
17
18 if (min_heap.size() > k) {
19 min_heap.dequeue();
20 }
21 }
22
23 const res: number[] = [];
24 while (!min_heap.isEmpty()) {
25 res.push(min_heap.dequeue()!.key);
26 }
27
28 return res;
29};Solution 2: Bucket Sort - Optimize follow up question
Approach
Phương pháp này tránh sử dụng heap và tận dụng một mảng các bucket để nhóm các phần tử theo tuần xuất hiện. Phương pháp này có Time complexity là O(n)
Các bước thực hiện:
Time and space complexity:
nums (tức là n)nums chỉ xuất hiện ở đúng một bucket (tương ứng với tần suất xuất hiện của nó)Solution
1function topKFrequent(nums: number[], k: number): number[] {
2 const num_map = new Map<number, number>();
3 for (const num of nums) {
4 num_map.set(num, (num_map.get(num) || 0) + 1)
5 }
6
7 const buckets: number[][] = Array(nums.length + 1).fill(null).map(() => []);
8
9 for (const [num, freq] of num_map.entries()) {
10 buckets[freq].push(num);
11 }
12 const res: number[] = [];
13 for (let i = buckets.length - 1; i >= 0 && res.length < k; i--) {
14 res.push(...buckets[i]);
15 }
16
17 return res;
18}