// use an array to save numbers into different bucket whose index is the 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);
}
// 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)
bucket[freq] = new LinkedList<>();
bucket[freq].add(n);
}
List<Integer> res = new LinkedList<>();
for(int i=bucket.length1; i>0 && k>0; i){
if(bucket[i]!=null){
List<Integer> list = bucket[i];
res.addAll(list);
k= list.size();
}
}
return res;
}
}
// 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()){
maxHeap.add(entry);
}
List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, Integer> entry = maxHeap.poll();
res.add(entry.getKey());
}
return res;
}
}
// use treeMap. Use freqncy as the key so we can get all freqencies in order
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)){
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;
}
}
3 Java Solution using Array, MaxHeap, TreeMap


@UpTheHell said in 3 Java Solution using Array, MaxHeap, TreeMap:
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) bucket[freq] = new LinkedList<>(); bucket[freq].add(n); } List<Integer> res = new LinkedList<>(); for(int i=bucket.length1; i>0 && k>0; i){ if(bucket[i]!=null){ List<Integer> list = bucket[i]; res.addAll(list); k= list.size(); } } return res; }
your first solution returns wrong answer for test case
[1, 1, 2, 2, 3, 3] k = 2
I think you need to handle tie breaking somehow in your code.

@csy0609 It's a shortcut for Comparator. You can spend some time to check Java 8 Lambda Expression. When you learn this, you do not want to write anonymous Comparator anymore.

one caveat is that this will add all the results by default for same frequency numbers. For example for input
[1,1,2,2,3,3,4], k=2
this will return[1,2,3]
where if we were expecting only top 2 elements (k=2) in increasing order. We could avoid that by returning the subList:
return res.subList(0,k);

@lzb700m said in 3 Java Solution using Array, MaxHeap, TreeMap:
your first solution returns wrong answer for test case
[1, 1, 2, 2, 3, 3]
k = 2I think you need to handle tie breaking somehow in your code.
Thanks, I have added your test case.

@1337c0d3r About the test case
[1, 1, 2, 2, 3, 3]
k = 2
when i got the result is [1,2], the OJ returns [1,3] and the code is not accepted.

@Goldenfong thanks. Turn out the test case was invalid because it has multiple answers. So I've removed it.

@UpTheHell said in 3 Java Solution using Array, MaxHeap, TreeMap:
axHeap so we can always poll a number
Why not have a min heap of size just "K"? Use peek() to look at the top which is the least out of the k elements and if your curr > peek() use poll to remove it and insert your current.

The array solution is pretty cool, but I think the heap and treemap solutions are O(NlogN) which is not what the question is asking. Theoretically if a data structure is keeping items already sorted, insertion to this structure cannot be O(1), it has to be at least O(logN) and since you're doing this for N items total complexity must be O(NlogN)

@UpTheHell said in 3 Java Solution using Array, MaxHeap, TreeMap:
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
maxHeap.add(entry);
}For this
for loop
, you can just use this one line codemaxHeap.addAll(map.entrySet());
.And it seems this solution is not efficient, using sortedSet is also a good choice.

Could some one explain why use MaxHeap instead of MinHeap? we are getting the largest k frequency, doesn't this mean we need to compare the smallest value in the heap to the next value so the larger one go into the heap? Using a MaxHeap, we would be comparing the largest value in the heap to the next value, which does not make sense to me. Thx.

@Oliiiviiiaaa
maxHeap is ordered on decreasing frequency of items....hence polling the heap gives top frequency entry first and he is retrieving all the top K entries and adding their respective elements to list.....hope its clear

@Chenlai
TreeMap is used for ordering the Frequent itemsets and map is used to store a frequency of particular element...
