21 ms Java solution with PriorityQueue


  • 1
    C
    import java.util.*;
    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            Arrays.sort(nums);
            PriorityQueue<Element> vals = new PriorityQueue<Element>(k, new ElementComparator());
            
            for(int i = 0; i < nums.length; i++) {
                int start = nums[i];
                int count = 1;
                while(i < nums.length-1 && nums[i+1] == start ) {
                    count++;
                    i++;
                }
                vals.add(new Element(start, count));
            }
            List<Integer> res = new ArrayList<Integer>(k);
            for (int i = 0; i < k; i++) {
                res.add(vals.poll().key);
            }
            return res;
        }
        
       class ElementComparator implements Comparator<Element>
        {            
             public int compare(Element c1, Element c2)
             {
                 Integer a1 = c1.value;
                 Integer a2 = c2.value;
                 
                 if(a1 > a2) {
                     return -1;
                 }
                 else if(a2 > a1)
                    return 1;
                 return 0;
             }
         }
        
        public class Element {
            int key, value;
            
            Element(int key, int val) {
                this.key = key;
                this.value = val;
            }
            public int compareTo(Element e) {
                
                if(this.value > e.value)
                    return 1;
                    
                else if(e.value > this.value)
                    return -1;
                return 0;
            }
    
        }
    }

  • 0
    H

    Your algorithm's time complexity must be better than O(n log n), where n is the array's size.


  • 0
    M

    Your solutions complexity is O(nlogn) as you used ''Arrays.sort(nums);'' in the first line.
    It can be reduced to O(k* logn) by using a hashmap to get the frequency count.
    Or, it can be further improved (O(n) ) by using Bucket Sort


Log in to reply
 

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