My Java Solution using PriorityQueue, beat 99%


  • 0
    F

    public class Solution {

    class Elements {
    	int value;
    	int num;
    
    	public Elements(int v, int n) {
    		value = v;
    		num = n;
    	}
    }
    
    class MyComparator implements Comparator<Elements> {
    	public int compare(Elements e1, Elements e2) {
    		return e2.num - e1.num;
    	}
    }
    
    public List<Integer> topKFrequent(int[] nums, int k) {
    	Arrays.sort(nums);
    	PriorityQueue q = new PriorityQueue(new MyComparator());
    	int total = 1;
    	int i;
    	for (i = 1; i < nums.length; i++) {
    		if (nums[i] == nums[i - 1]) {
    			total++;
    		} else {
    			q.add(new Elements(nums[i - 1], total));
    			total = 1;
    		}
    	}
    	q.add(new Elements(nums[i - 1], total));
    	List<Integer> res = new ArrayList();
    	for (i = 1; i <= k; i++) {
    		res.add(((Elements) q.remove()).value);
    	}
    	return res;
    }
    

    }


  • 0
    M

    Arrays.sort takes O(nlogn) time.
    An alternate solution is to count the values and store it in a hashmap and then put it in the priority queue.
    Something like this

    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            if(nums==null || nums.length==0 || k==0){
                return null;
            }
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            Queue<Integer> q = new PriorityQueue<Integer>( new Comparator<Integer>(){
                @Override
                public int compare(Integer i1, Integer i2){
                    if(map.get(i1)<map.get(i2)){
                        return 1;
                    }else if(map.get(i1)>map.get(i2)){
                        return -1;
                    }
                    return 0;
                }
                });
            
            for(int i=0; i<nums.length; i++){
                if(!map.containsKey(nums[i])){
                    map.put(nums[i],1);
                }else{
                    map.put(nums[i],map.get(nums[i])+1);
                }
            }
            for(Map.Entry<Integer,Integer> val : map.entrySet()){
                q.offer(val.getKey());
            }
            List<Integer> res = new LinkedList<Integer>();
            int count=0;
            while(count<k && !q.isEmpty()){
                res.add(q.poll());
                count++;
                
                
            }
            return res;
            
        }
    }
    

Log in to reply
 

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