## 347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Example 2:

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

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(nlogn), where n is the array's size.

Thoughts:

1. Bucket sort:
2. MaxHeap Implementation (BUT O(nlogn))
3. TreeMap: Use freq as the key so can get freq in order

Code

``````class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
m = [0] * (len(nums) + 1)
cnt = collections.Counter(nums)
for i in range(len(m)):
m[i] = []

for v in cnt:
m[cnt[v]].append(v)
res = []
for l in (m[::-1]):
res += l
if len(res) >= k: break
return res
``````

Code:

``````public class 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);
}

// corner case: if there is only one number in nums, we need the bucket has index 1.
List<Integer>[] bucket = new List[nums.length+1];
for(int n:map.keySet()){
int freq = map.get(n);
if(bucket[freq]==null)
}

for(int i=bucket.length-1; i>0 && k>0; --i){
if(bucket[i]!=null){
List<Integer> list = bucket[i];
k-= list.size();
}
}

return res;
}
}
``````

Code: max heap T:O(nlogn); S:O(n)

``````// use maxHeap. Put entry into maxHeap so we can always poll a number with largest frequency
public class 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);
}

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

List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, Integer> entry = maxHeap.poll();
}
return res;
}
}
``````

Code: Java TreeMap: T:O(nlogn); S:O(n)

``````public class 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)){
}
}

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

Code: Python having fun...

``````class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
return zip(*collections.Counter(nums).most_common(k))[0]
``````