forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
347-Top-K-Frquent-Elements.js
49 lines (43 loc) · 1.22 KB
/
347-Top-K-Frquent-Elements.js
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {
let map = new Map();
let res = [];
let bucket = Array.from({ length: nums.length + 1 }, () => []); // to create unique arrays
// storing frequency of numbers in a map
for (let n of nums) {
map.set(n, map.has(n) ? 1 + map.get(n) : 1);
}
// Poppulate the bucket with numbers in frequency
// as the index of the bucket
for (const [key, value] of map.entries()) {
bucket[value].push(key);
}
for (let i = bucket.length - 1; i >= 0; i--) {
if (bucket[i].length > 0) {
for (let n of bucket[i]) {
res.push(n);
if (res.length === k) return res;
}
}
}
};
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequentNLogN = function(nums, k) {
const map = nums.reduce((acc, num) => {
const currentNumber = acc[String(num)];
acc[num] = currentNumber ? currentNumber + 1 : 1;
return acc;
}, {});
return Object.entries(map)
.sort(([, countA], [, countB]) => countB - countA)
.slice(0, k)
.map(([num]) => +num);
}