Java Heap Solution, 9 ms beats 99%


  • 0
    Z

    The idea here is:

    • Count the frequency of the characters in the string
    • Add the <character, count> pairs into a heap, which is sorted by the descending order of count
    • Poll out the pairs one-by-one and construct the string using the StringBuilder.

    The complexity is O(N+NlogN+N) = O(NlogN), N is the string length.

    public class Solution {
        //Definition of pairs
        class Charcount{
            int count;
            char c;
            public Charcount(int n,char c){
                this.count = n;
                this.c = c;
            }
        }
        public String frequencySort(String s) {
            //Count frequency
            int[] charmap = new int[128];
            for(char c:s.toCharArray()){
                charmap[c]++;
            }
            //Construct heap
            Comparator<Charcount> cmp = new Comparator<Charcount>(){
                public int compare(Charcount c1,Charcount c2){
                    return c2.count-c1.count;
                }
            };
            Queue<Charcount> q = new PriorityQueue<Charcount>(1,cmp);//Use a constant capacity to avoid error when s==""
            
            for(int i = 0;i<charmap.length;i++){
                if(charmap[i]>0){
                    q.offer(new Charcount(charmap[i],(char)(i)));
                }
            }
            //Construct string
            StringBuilder sb = new StringBuilder();
            while(!q.isEmpty()){
                Charcount c = q.poll();
                char[] line = new char[c.count];
                Arrays.fill(line,c.c);
                sb.append(new String(line));
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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