Leetcode 347 - Top K frequent elements

Note:

  • Cannot use normal sort methods because of the limit of time complexity.
  • Use bucket sort because its average time complexity is O(n).
  • Use map to track the frequencies.
  • Iterate map and assign num which has the same frequency to bucket[frequency].
  • Iterate backwards and find k elements as the result.

Question:

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
let map = new Map();
let result = [];
let bucket = [];
for (let i = 0; i < nums.length; i++) {
if (!map.has(nums[i])) {
map.set(nums[i], 1);
} else {
map.set(nums[i], map.get(nums[i]) + 1);
}
}
map.forEach((value, key) => {
if (!bucket[value]) {
bucket[value] = [key];
} else {
bucket[value].push(key);
}
})
for (let i = bucket.length - 1; i >= 0 && k > 0; i--) {
if (bucket[i]) {
for (const char of bucket[i]) {
if (k === 0) break;
result.push(char);
k--;
}
}
}
return result;
};