Java PriorityQueue Solution


  • 0

    The idea is to store char -> frequency pairs in an int array. Then for the frequency not equals to 0, we add this char to PriorityQueue. Also we need to rewrite compare method in Comparator to make sure we can get these in descending order.

    public class Solution {
        public String frequencySort(String s) {
            int[] arr = new int[256];
            for (char ch : s.toCharArray()) {
                arr[ch]++;
            }
            PriorityQueue<Integer> pq = new PriorityQueue<>(
                    new Comparator<Integer>() {
                        public int compare(Integer n1, Integer n2) {
                            return arr[n2] - arr[n1];
                        }
                    }
            );
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > 0) {
                    pq.add(i);
                }
            }
            StringBuilder res = new StringBuilder();
            while (pq.size() != 0) {
                int tmp = pq.poll();
                for (int i = 0; i < arr[tmp]; i++) {
                    res.append((char)tmp);
                }
            }
            return res.toString();
        }
    }
    

Log in to reply
 

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