*Java* straightforward O(N + (N-k)lg k) solution


  • 31
    E

    Idea is very straightforward:

    • build a counter map that maps a num to its frequency
    • build a heap/priority queue that keeps track of k most significant entries
    • iterate through the final heap and get the keys

    Code in Java:

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> counterMap = new HashMap<>();
        for(int num : nums) {
            int count = counterMap.getOrDefault(num, 0);
            counterMap.put(num, count+1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> a.getValue()-b.getValue());
        for(Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
            pq.offer(entry);
            if(pq.size() > k) pq.poll();
        }
        
        List<Integer> res = new LinkedList<>();
        while(!pq.isEmpty()) {
            res.add(0, pq.poll().getKey());
        }
        return res;
    }

  • 6
    K

    In the end we have to poll all the remaining elements out of the heap and the time for this process shall be considered too, so I think the time complexity should be O(N + Nlgk), or just O(Nlgk).


  • -1
    E

    The heap contains k elements, so it is k lg k :-)


  • 0
    K

    I mean, O(N + (N-k)lgk + klgk) = O(N + Nlgk).


  • 0
    E

    My bad. Yes, I see ur point now. You are absolutely correct.


  • 3
    C

    The total time complexity I think should be O(N+k+(N-k)lgk), where N is the time spent on traversing over the map, k is the time to build heap, and (N-k)lgk is the time to insert the remaining (N-k) elements.


  • 0
    K

    What does this part mean in the Priority queue constructor (a, b) -> a.getValue()-b.getValue()


  • 0
    C

    I have the same question.


  • 4
    H

    (a, b) -> a.getValue()-b.getValue(), is a way of implementing the abstract method required for using the comparator interface. This is called lambda expressions introduced in Java8.


  • 0
    S

    @codingcoconut In java 8 we have something called as Functional Interfaces (an interface with only one abstract method). Now using lambdas, we can implement the method of that functional interface as shown above. It is a very cool addition to Java 8.


  • 5
    L

    I dont think you reached (N-k)lgk. Though you maintained the size of que to be k, you still enque N elements which typically takes logk time. so, I believe it is nlgk for the below for loop. More over, you do the poll() when the size is larger. Actually, we only need to poll() if the peek() value is larger than the current value. That will save some time too.

    for(Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
            pq.offer(entry);
            if(pq.size() > k) pq.poll();
        }
    

    So, in total, it should be O(N) + O(nlogk) + O(klogk).
    My solution for your designed complexity is as follows. Of course, in the worst cast, both of our solution is the same.

    for(Map.Entry<Integer, Integer> ent : map.entrySet()){
      if(que.size()<k) que.offer(ent);
           else{
               if(!que.isEmpty() && que.peek().getValue()<ent.getValue()){
                   que.poll();
                   que.offer(ent);
           }
      }
    }
    

  • 0
    L

    @liang54 I do think so. In Java PriorityQueue source offer() call siftUp() which is O(logn).


Log in to reply
 

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