Java, beats 98%, PriorityQueue solution


  • 0
    D

    I use a priority queue to sort, then rebuild the string, easy to understand the code below:

    public class Solution {
        
        // inner class
        private static class Element implements Comparable<Element>
        {
            private int freq;
            private char c;
            
            public Element(int freq, char c)
            {
                this.freq = freq;
                this.c = c;
            }
            // override compareTo method
            public int compareTo(Element o2)
            {
                if (this.freq > o2.freq) return -1;
                if (this.freq == o2.freq) return 0;
                return 1;
            }
        }
            
        public String frequencySort(String s) 
        {
            int[] letter = new int[256];
            // O(n), record frequency of each character
            for (char c : s.toCharArray())
            {
                letter[c]++;
            }
            
            // priority queue used to sort each character corresponding to its frequency
            Queue<Element> q = new PriorityQueue<>();
            
            // constant time
            for (int i = 0; i < 256; i++)
            {
                if (letter[i] != 0) q.offer(new Element(letter[i], (char)i));
            }
            
            // rebuild string
            char[] res = new char[s.length()];
            int i = 0;
            while (!q.isEmpty())
            {
                Element e = q.poll();
                for (int j = i; j < i + e.freq; j++)
                {
                    res[j] = e.c;
                }
                i += e.freq;
            }
            
            return new String(res);
        }
    }
    

Log in to reply
 

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