3 Java Solution using Array, MaxHeap, TreeMap


  • 78
    // 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.length-1; 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
    C

    PriorityQueue<Map.Entry<Integer, Integer>> maxHeap =
    new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));

    Thanks for sharing these brilliant thoughts but I have a question, what does
    "(a,b)->(b.getValue()-a.getValue())" this part mean?


  • 0
    L

    @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.length-1; 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.


  • 5

    @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.


  • 4
    H

    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);


  • 0

    @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 = 2

    I think you need to handle tie breaking somehow in your code.

    Thanks, I have added your test case.


  • 0
    G

    @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.


  • 2

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


  • 3
    M

    @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.


  • 6
    M

    @UpTheHell

    For the second method, the time complexity is O(NlgN), right? If all numbers are distinct, the add() for priority queue is O(lgN). Then the second for loop will be O(NlgN).


  • 7
    R

    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)


  • 0

    @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 code maxHeap.addAll(map.entrySet());.

    And it seems this solution is not efficient, using sortedSet is also a good choice.


  • 0
    C

    Can any one here tell me why the author not use a single TreeMap in the "TreeMap method" but use both HashMap and TreeMap?


  • 0
    O

    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.


  • 0
    C

    @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


  • 0
    C

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


  • 0
    O

    @code4life Yeah. That helps! I missed the retrieving part. Sorry to bother. Thx!


  • 0
    J

    Thanks for sharing!


  • 0
    N

    Iterating through the list to put the values in a map makes the complexity O(n)?
    '''
    for(int n: nums){
    map.put(n, map.getOrDefault(n,0)+1);
    }
    '''


  • 1
    S

    Using array is O(n), MaxHeap is O(nlogn). Am I right? What is the time complexity for using TreeMap? Thanks for sharing the different implements.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.