Java easy understand solution, O(n) using counting sort, beat 99%.


  • 0
    N
    public class Solution {
        
        public String frequencySort(String s) {
            //counting sort
            int n = s.length();
            int[] charCount = new int[256];
            char[] cs = s.toCharArray();
            char[] ans = new char[n];
            //Count the char
            for(char c: cs){
                charCount[c]++;
            }
            
            //counting sort the frequency since it has range from 1 to n.
            int[] count = new int[n+1];
            for(int i:charCount){
                if(i>0){
                    count[i]+=i;                
                }
            }
            
            for(int i=1; i<count.length; i++){
                count[i] += count[i-1];
            }
            
            for(int i=0; i<256; i++){
                if(charCount[i] > 0){
                    int c = charCount[i];
                    // small different from normal counting sort, in case the same char has to be together
                    while(c>0){
                        ans[n-count[charCount[i]]] = (char)i;
                        count[charCount[i]]--;
                        c--;
                    }
                    
                }
            }
            
            return new String(ans);
        }
    }
    

  • 0
    P

    @nightswatch Thanks for the share. Can you explain the step -
    for(int i=1; i<count.length; i++){
    count[i] += count[i-1];
    }
    Thanks.


  • 0
    N

    @pantherNation
    Basically, it sums up the counts for each value, so you can get a sense of how many values less than a certain value.

    You can also check and learn counting sort from the following links:

    code: http://www.geeksforgeeks.org/counting-sort/
    video: https://www.youtube.com/watch?v=7zuGmKfUt7s


Log in to reply
 

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