Press "Enter" to skip to content

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:

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

Example 2:

```Input: nums = [1], k = 1
Output: [1]
```

Constraints:

• `1 <= nums.legth <= 105`
• `k` is in the range `[1, the number of unique elements in the array]`.
• It is guaranteed that the answer is unique.

Solution 1: Bucket Sort O(n); O(n)

• Use a HashMap to store each number and its frequency.
• Use bucket array to save numbers into different bucket whose index is the frequency
``````/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
let counts = new Map();
let buckets = [];
for (let i = 0; i <= nums.length; i++)
buckets.push([]);

// count frequent of the elements
for (let num of nums) {
if (counts.has(num)) {
counts.set(num, counts.get(num) + 1);
} else {
counts.set(num, 1);
}
}
// put them into buckets by frequent
for (let [key, value] of counts) {
buckets[value].push(key);
}
// fetch the larget frequest bucket first, until reach k
let ans = [];
for (let i = buckets.length - 1; i > 0 && ans.length < k; i--) {
if (buckets[i] !== null) ans.push(...buckets[i]);
}
return ans;
};``````

Solution 2: maxHeap O(n log n); O(n)

Javascript does not have a standard heap / priority queue data structure that you can use out of the box.

See Java solution:

``````public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}

Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}

PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new
PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
maxHeap.offer(entry);
}

while (res.size() < k) { //important
res.add(maxHeap.poll().getKey());
}
return res;
}``````

Solutoin 3: TreeMap (n log n); O(n)

Use treeMap. Use freqncy as the key so we can get all freqencies in order

See Java solution:

``````public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}

TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
for(int num : map.keySet()){
int freq = map.get(num);
if(!freqMap.containsKey(freq)){
freqMap.put(freq, new LinkedList<>());
}
freqMap.get(freq).add(num);
}

List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
res.addAll(entry.getValue());
}
return res;
}``````