Bucket sort using PriorityQueue


  • 0
    J

    using an array list of priority queue to store all strings with same frequency and store them in a lexical order.

    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            List<String> res = new ArrayList<>();
            Map<String, Integer> map = new HashMap<>();
            int occurance = 0;
            for (String str : words) {
                map.put(str, map.getOrDefault(str,0)+1);
                occurance = Math.max(occurance, map.getOrDefault(str,0));
            }
            PriorityQueue<String>[] buckets = new PriorityQueue[occurance+1];
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                if (buckets[entry.getValue()] == null ) {
                    buckets[entry.getValue()] = new PriorityQueue<String>(new Comparator<String>(){
                        public int compare(String a, String b) {
                            return a.compareTo(b);
                        }
                    });   
                }
                buckets[entry.getValue()].add(entry.getKey());
            }
            int len = buckets.length;
            for (int i=len-1; i>=0 ; i--) {
                if (buckets[i] == null) continue;
                while (res.size() < k && buckets[i].size() != 0) {
                    res.add(buckets[i].poll());
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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